BOJ 백준 [2003] 수들의 합 2

백준 온라인 2003번 문제

---

IDEA 1

문제에서 주어진 N의 경우 10,000이다. 

그리고 각각의 A[x]는 30,000을 넘지 않는 자연수라고 하였다.

 

그렇다면 N의 값이 최대일때, 모든 A[x]를 다 더하여도 300,000,000을 넘지 않는다.

즉, 최댓값이 2,147,438,647인 int형의 최댓값보다 작다.

 

만약 아래와 같이 배열을 만든다고 가정하고 생각하자.

 

 int sums[MAX_N]
 
 for(int i = 0; i < N; i++) {
     sums[i] = input[i] + sums[i-1] //현재 입력 값과 이전의 입력값들을 모두 더한 배열을 만들자.
}

 

여기서 sums 배열에서 현재의 위치 i와 이전의 위치 j를 이용하여 입력 값 M을 찾는 것을 생각해보자.

for(int i = 0; i < N; i++) {
    for(int j = 0; j < i; j++) {
        int tempM = sums[i] - sums[j];
        if(tempM == M) {
            count++;
            break;
        } else if (tempM < M) {
            break;
        }
    }
}

주어진 배열들의 값은 자연수이므로 만약  tempM이 주어진 M값보다 작아진다면 M값이 나올 없으므로 위와 같이 

문제를 해결할 수 있다.

 그렇다면 위와 같이 코드를 작성했을 때 시간 복잡도에 대해 고민해보자.

 

i = 1 --> j = 0

i = 2 --> j = 1

....

즉, 0+1+2+..............+N-1과 같이 실행을 한다. 이는 O((N-1)*(N)/2)의 시간 복잡도를 가진다. 

즉 , O(N^2) 이므로 애매하다....

백준 온라인 저지 2003번 문제 풀이 결과

좀... 찝찝하다. 다른 방법에 대해 고민해보자.

---

IDEA 2

two pointer로 문제에 접근해보자.

[figure 2-1]

위와 같이 배열에서 two pointer로 탐색을 할 경우,

 

1. sum의 값이 M보다 작다면 i의 위치를 오른쪽으로 옮겨 sum값을 증가시켜주자.

2. sum의 값이 M보다 크거나 같다면 j의 위치를 오른쪽으로 옮게 sum값을 감소시켜주자.

 

int i, j;
int sum = 0;
 
i = j = 0;
 
while (j < N) {
    if (sum < M) {
        if (j >= N) {
            break;
        }
        sum += input[i++];
    }
    else if (sum == M) {
        count++;
        sum -= input[j++];
    }
    else {
        sum -= input[j++];
    }
}

위와 같이 문제를 해결했을 때, 시간 복잡도는 O(N)이므로 주어진 시간내에 문제를 해결할 수 있다.

 

백준 온라인 저지 2003번 문제 풀이 결과