[백준/BOJ/C언어] 1806번 :: 부분합

문제 링크 :: https://www.acmicpc.net/problem/1806

---

 Solution

 

  문제 이름처럼 부분 합을 이용해서 푸는 문제. 그래서 일단 sum 배열에 부분 합을 구해 줬다. 그리고 나서는 어떻게 시간 초과가 나지 않으면서 합이 S 이상인 구간 합 중 가장 길이가 짧은 것을 구하느냐가 관건이었다. 다른 사람들은 어떻게 풀었는지 모르겠지만 나는 S 이상의 부분 합이 나타나는 부분 합을 발견하면 그 인덱스를 기준으로 가장 짧은 구간 합(j가 i-1인 경우)부터 계산하면서 그 값이 S 이상이 되면 정답 후보 배열(sol)에 길이를 저장해 주도록 했다. 가장 짧은 구간 합부터 구하니까 S 이상인 값을 발견하면 바로 반복문을 탈출한다. 만약 가장 짧은 구간 합이 S 이상이면 굳이 나머지 구간 합을 살펴볼 필요가 없으므로. 그리고 나서 그 배열 중 가장 값이 작은 배열이 정답. 그런데 만약 가능한 구간 합이 없어 min이 초기값에서 변경되지 않았다면 문제 지시대로 0을 출력하도록 한다. 그래서 일단 통과는 했는데... 반복문만 보면 시간 복잡도가 O(N^2)인데 어떻게 시간 초과가 안 났는지 잘 모르겠다. 조건문 때문에 그 정도까지는 되지 않는 건가? inchworm이라는 알고리즘을 사용한 사람들도 있던데, 읽어 봐도 이해가 되지 않아서 일단 보류했다. 다음에 제대로 공부해 봐야 할 듯.

---

 Code

#include <stdio.h>
long long sum[100001];
int sol[100001];
 
int main(void) {
    int N, i, j, num, min = 100000;
    long long S;
    scanf("%d %lld", &N, &S);
 
    for (i = 1; i <= N; i++) {
        scanf("%d", &num);
        sol[i] = -1;
        sum[i] = sum[i - 1] + num;
    }
 
    for (i = 1; i <= N; i++) {
        if (sum[i] >= S) {
            for (j = i-1; j >= 0; j--) {
                if (sum[i] - sum[j] >= S) {
                    sol[i] = i - j;
                    break;
                }
            }
        }
    }
    
    for (i = 1; i <= N; i++) {
        if (sol[i] < min && sol[i] != -1) {
            min = sol[i];
        }
    }
 
    if (min == 100000) {
        printf("0");
    }
    else {
        printf("%d", min);
    }
 
    return 0;
}

---

 Related

2019/07/27 - [코학/알고리즘] - [알고리즘] Prefix sum(구간 합)에 대해 알아보기