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

처음에 DP라고 생각하고 풀어서 맞췄다.

알고보니 투 포인터 문제였다.

투 포인터가 무엇인지 몰랐는데 이 문제가 대표적인 투 포인터 문제라고 한다.

 

투 포인터란?

1차원 배열에서 두 개의 포인터를 가지고 조작하면서 원하는 값을 얻는 알고리즘이다. 이 때 배열의 모든 원소는 자연수여야만 투 포인터 알고리즘이 가능하다.

 

문제 접근방식

처음 내 풀이는 DP로 풀었다.

시간 제한을 보아도 DP밖에 방법이 떠오르지 않았다.

동적 계획법 Bottom Up 방식을 사용해서 문제를 풀었다.

그리고 각 자리수가 증가할 때마다 해당 다음 번째 수에 있는 값을 더해 나간다고 생각하고 풀었다.

 

예시 입력을 예로들면, dp가 결과값을 담는 배열이고 num이 각 값을 담는 배열이라 할 때

N = 10, M = 5이고 원소가 1 2 3 4 2 5 3 1 1 2이면,

• 처음 자기 자신만 사용하는 경우 : dp[1] = 1, dp[2] = 2 + ... + dp[10] = 2가 된다.
• 자기 자신에서 다음번째까지 사용하는 경우 : dp[1] = dp[1] + num[2], dp[2] = dp[2] + num[3] + ... + dp[9] = dp[9] + num[10]

이런 식으로 dp 값을 업데이트 해 나가면서, 만일 값이 찾는 값과 같은 값이 나온다면 결과에 하나를 더해준다.

 

막상 풀어보니, 시간이 꽤 오래걸리는 것 같아서 다른 방식이 있는지, 잘못 푼건지 알고리즘 분류를 확인해보니

투 포인터 알고리즘을 사용하는 것이었다.

 

그냥 넘어갈 수도 있었지만, 한 번 푼 문제는 다시 풀 기회가 없을 것 같아서 투 포인터 알고리즘을 써보기로 했다.

 

문제풀이

#include <iostream> using namespace std; int numCnt, findNum; int num[10001]; int dp[10001]; int result; int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);     cin >> numCnt >> findNum;     int input;     for (int i = 1; i <= numCnt; i++) {         cin >> input;         num[i] = input;         dp[i] = input;         if (num[i] == findNum) { result++; }     }     for (int i = 1; i <= numCnt; i++) {         for (int j = 1; j <= numCnt; j++) {             if (j + i > numCnt) { break; }             dp[j] = dp[j] + num[j + i];             if (dp[j] == findNum) { result++; }         }     }     cout << result;     return 0; }

우선 DP로 짠 코드는 위와 같다.

DP 문제는 아니므로 설명은 접근방식에서 했던 것으로 대체하고 DP 풀이는 생략하겠다.

 

이 문제에서 투 포인터에 대해 어떻게 적용되는지 살펴보자면,

투 포인터는 시작, 끝 그리고 부분 합이라는 개념이 적용된다.

시작과 끝은 처음에 항상 첫번째 인덱스(보통 0번째지만 나는 첫번째로 사용한다.)를 나타낸다.

다음 테스트 케이스로 예시를 들겠다.

10 5 1 2 3 4 2 5 3 1 1 2

1. start = 1, end = 1, sum = 0이다. sum < 5이므로, end 포인터를 하나 증가시키며 첫번째 idx에 있는 원소를 sum에 더해준다. sum = 0 -> 1이 된다.
2. start = 1, end = 2, sum = 1이다. sum < 5이므로, end 포인터를 하나 증가시키며 두번째 idx에 있는 원소를 sum에 더해준다. sum = 1 -> 3이 된다.
3. start = 1, end = 3, sum = 3이다. sum < 5이므로, end 포인터를 하나 증가시키며 세번째 idx에 있는 원소를 sum에 더해준다. sum = 3 -> 6이 된다.
4. start = 1, end = 4, sum = 6이다. sum >= 5이므로, start 포인터를 하나 증가시키며 첫번째 idx에 있는 원소를 sum에서 빼준다. sum = 6 -> 5가 된다.
5. start = 2, end = 4, sum = 5이다. sum == 5이므로, 결과값을 하나 증가시키고 start 포인터를 하나 증가시키며 두번째 idx에 있는 원소를 sum에서 빼준다. sum = 5 -> 3이 된다.
6. ...

다음과 같은 방식으로 진행이 되며, end가 원소의 개수보다 커질때 반복문을 종료시켜주면 된다.

 

코드를 살펴보자.

사용한 STL과 변수

원소의 개수 numCnt와 찾는 수 findNum이 있다.

그리고 원소를 담을 배열 arr와 결과값을 출력할 result변수가 있다.

 

메인함수 - 1

원소의 개수와 찾는 수를 입력받고 각 원소를 입력받는다.

 

메인함수 - 2 / 투 포인터

이 부분이 투 포인터를 쓰는 메인함수의 아랫부분이다.

시작 인덱스와 끝 인덱스를 1로 초기화 해준다. (0번째 배열부터 쓰는 사람은 0으로 초기화 해주어야 한다.)

 

그리고 반복분의 조건에 startIdx <= endIdx라고 되어있는데, 사실 이건 당연한 것으로, while(true)와 같은 의미이다.

이유는 sum이 0이나 findNum보다 작아지게 되면 endIdx를 증가시키게 되므로, startIdx는 당연히 endIdx보단 작아지게 된다.

 

투 포인터를 구현할 때에는 반복문의 순서가 상당히 중요하다.

1. sum이 findNum보다 크거나 같다면 sum에서 start가 가리키는 원소를 빼주고 start에 1을 더해준다.
2. sum이 findNum보다 작다면, end가 가리키는 원소를 더해주고 end에 1을 더해준다. 이 때, end가 증가되기 전에 이미 end가 원소의 개수보다 커져있다면 반복문을 종료시킨다. end가 원소 개수보다 이미 커져있다는 뜻은 뒤에 원소가 더이상 존재하지 않는다는 뜻이므로 확인할 필요가 없다.
3. 현재 sum이 찾는 수와 같다면 결과값에 1을 더해준다.

처음에 DP로 맞추고, 투 포인터 알고리즘을 공부하면서 코드를 제출하면서 공부했더니 너무 많이 틀려버렸다.

새로 알게된 알고리즘으로, 잊지말고 머리속에 담아둬야겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.