[C++] 백준 2003 수들의 합 2

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

1. 서론

 

이 문제는 투 포인터 알고리즘의 대표적인 예시라고 한다...

 

2. 문제 풀이

 

n개의 배열이 있다. 배열의 i~j의 값을 모두 더하면 m이 되는 경우의 수를 구하는 문제이다.

문제의 예제로 예를 들어보자

 

n = 10, m = 5

배열: 1 2 3 4 2 5 3 1 1 2

 

그럼 이 중에서 

 

2 + 3 = 5

5 = 5

1 + 1 + 2 = 5

 

이므로 경우의 수는 3이다.

 

나는 진짜 쉽게 풀었는데 투 포인터 알고리즘이 뭔지 몰라서 그냥 되는대로 풀었다. 

그냥 문제 그대로 배열을 i, j로 돌면서 배열값을 더해서 5가 되면 카운트하고 그런 식으로...

 

참조: ssungkang.tistory.com/entry/Algorithm-Two-Pointers-투-포인터

[Algorithm] Two Pointers, 투 포인터

(투 포인터 알고리즘으로 짠 코드를 보고 싶은 사람은 위 링크 참조)

 

하지만 투 포인터 알고리즘은 약간 다르다. 원리 자체가 크게 다른 것은 아닌데

내가 푼 경우는 배열을 순서대로 돈다. (완전탐색)

 

1 2 3 4 2 5 3 1 1 2

 

이 경우에 1 + 2를 해보고 또 1 + 2 + 3을 해보고 5가 안 나오면 다시 2 + 3을 해보고 시도를 해가며 범위를 좁혀가는 식이라면 투 포인터 알고리즘은 말 그대로 i와 j가 앞뒤로 움직인다. 움직이는 기준은 m이 됐나 안됐나 이다. m보다 크면 다음으로 넘어가고 작으면 더해보고... 

한 마디로 내가 한 것보다 훨씬 효율적이다. (모든 경우를 시도해보지 않으므로,,,) 그래서 실행시간이 훨씬 작다.

근데 이해는 했는데 다음에 다른 문제가 나오면 내가 잘 활용해서 풀 수 있을지는... 자신이 없다 ㅠ

 

3. 코드 설명

 

#include <iostream>

using namespace std;

int main()
{
    int n, m, i, j, x, c = 0;
    int a[10000];

    cin >> n >> m;

    for (i = 0; i < n; i++)
        cin >> a[i];

    for (i = 0; i < n; i++)
    {
        x = 0;
        for (j = i; j < n; j++)
        {
            x += a[j];
            if (x == m)
            {
                c++;
                break;  
            }
        }
    }

    cout << c << endl;
}

 

배열을 입력받고 i~j까지 돌면서 m인지 아닌지 본다. m인 경우에는 count를 하고 반복문을 멈춘다. (더 도는 것은 낭비이므로)

그리고 i의 범위를 점점 줄여가며 뒤의 배열에서도 i~j의 합이 m인지 확인하는 것이다.