[BaekJoon 1940번] 주몽(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1940번: 주몽

 

 

[문제 설명]

 

 

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

 

 

[출력]

 

 

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
6 9 2 7 4 1 5 3	2

 

 

[문제 풀이]

 

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

➜ 1차원 배열에서 2개의 포인터를 사용하여 원하는 결과 값을 얻는 알고리즘이다.

 

문제는 N개의 재료들이 주어지고 2개의 재료를 선택했을 때 M이 되면 갑옷을 만들 수 있다.

 

입출력 예로 설명해보자면

1. 우선 N개의 재료들을 오름 차순으로 정렬한다.

2. 2개의 변수(start, end)을 선언한다.

3. start는 배열의 맨 앞 원소를 가르키고 end는 다음 배열의 원소를 가리키도록 한다.

4. start 변수 값과 end 변수 값을 더했을 때 M이 되는지 확인한다.

4-1. M이 된다면 만들 수 있는 갑옷의 갯수를 1 증가 시킨다.

4-2. M이 되지 않는다면 end 변수를 N 이전 인덱스까지 이동시켜가면서 4번을 반복한다.

5. 만약 end 변수가 배열의 끝에 다다르게 되면 start 변수는 start 변수가 가리키던 다음 배열의 원소를 가리키고

end 또한 start 변수의 다음 배열의 원소를 가리키도록 하여 4번을 반복한다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    int N; cin >> N;
    int M; cin >> M;
    vector<int> v;
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        v.emplace_back(n);
    }
    sort(v.begin(), v.end());
    int start, end = 0;
    int ans = 0;
    for(int i = 0; i < N; ++i) {
        start = i;
        end = i + 1;
        while(end < N) {
            if(v[start] + v[end] == M) ans += 1;
            end += 1; 
        }
    }
    cout << ans;
    return 0;
}