[C/C++] 백준 #1940 주몽(두개의 포인터)

두개의 조합에 의해서 M인 값을 얼마나 많이 찾을 수 있는 가에 대한 문제입니다.

 

주몽

 

예를 들어서, 

2 7 4 1 5 3

이라는 재료가 주어지고, 조합해서 만들어야 하는 갑옷이 9의 값을 가져야 한다면,

 

먼저 정렬을 수행합니다.

1 2 3 4 5 7

 

그러면 두개의 합을 왼쪽편과 오른쪽편을 이용해서 구해보도록 합니다.

1) 1 과 7을 더하면 8이므로 숫자가 부족하므로 왼쪽을 1 증가시킵니다.

2) 2 와 7을 더하면 9이므로 답을 1 증가시키고, 왼쪽을 1 증가, 오른쪽을 1 감소합니다.

3) 3과 5를 더하면 8이므로, 왼쪽을 1 증가합니다.

4) 4와 5를 더하면 9이므로, 왼쪽은 1 증가, 오른쪽을 1 감소합니다.

5) 왼쪽의 포인터와 오른쪽 포인터가 교차했으므로 종료합니다.

 

그러면 총 2개의 갑옷을 만들 수 있다는 것을 알 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1940
//        - by Aubrey Choi
//        - created at 2019-07-04
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, m, i, j, v[15000], ans = 0;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++) scanf("%d", &v[i]);
    std::sort(v, v + n);
    i = 0, j = n - 1;
    while(i < j)
    {
        if(v[i] + v[j] == m) ans++, i++, j--;
        else if(v[i]+v[j] < m) i++;
        else j--;
    }
    printf("%d\n", ans);
    return 0;
}