주몽의 명령(백준 1940)

1. 문제이해

재료개수(N)를 가지고 갑옷을 만드는데 필요한 수(M)를 몇 개 만들 수 있는지 갑옷을 만들기 위해서는 두 개의 재료를 합침

 

ex) N=3, M=5, N의 재료 1, 3, 4  -> 1 + 4 = 5 총 1개의 갑옷을 만들 수 있음

사용된 재료는 사라짐

 

2. 문제분석

재료를 정렬시킨 후 투 포인터를 배열의 양쪽 끝에 위치시킴

2	7	4	1	5	3
start					end

 

1	2	3	4	5	7
start					end

 

start와 end 포인터가 가리키는 값을 더해서 M과 동일하면 두 개의 재료를 버리고 다음 위치로 이동

 

start와 end를 더했을 때 M보다 작다면 start 포인터 위치를 한 칸 증가시키고 end와 더해줌 

(M보다 작으니까 값을 조금씩 키워서 M과 맞추기 위해 작은 수 중에서 그 다음으로 큰 수를 더해줌)

 

start와 end를 더했을 때 M보다 크다면 end 포인터 위치를 한 칸 감소하고 start와 더해줌

(M보다 크니까 값을 조금씩 줄여서 M과 맞추기 위해 큰 수 중에서 그 다음으로 작은 수를 더해줌)

 

 

3. 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 1.입력
    int N; // 재료 개수 
    int M; // 갑옷을 만드는데 필요한 수 
    cin >> N >> M;

    int* num = new int[N]; // N개의 재료들이 가진 번호
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }

    // 작은 수부터 오름차순 정렬 
    sort(num, num + N);

    int start_index = 0; // 작은수 번호 
    int end_index = N - 1; // 큰수 번호
    int count = 0; // 갑옷을 만들 수 있는 개수

    // start_index가 end_index의 값과 똑같거나 커질때 반복문 종료
    while (start_index < end_index) {
        // 두 개의 재료합이 갑옷을 만드는데 필요한 수와 동일한 경우
        if (num[start_index] + num[end_index] == M) {
            // 갑옷을 만들기 위해서 재료를 사용했으니까 다음 재료로 넘어가는 작업
            count++;
            start_index++;
            end_index--;            
        }
        else if (num[start_index] + num[end_index] < M) 
        {
            // M보다 작으면 작은번호 index를 1증가
            // 작은 수 중에서 그 다음으로 큰 수를 더해서 순서대로 확인
            start_index++; 
        }
        else if (num[start_index] + num[end_index] > M)
        {
            // M보다 작으면 큰번호 index를 1감소
            // 큰번호 중에서도 그 다음으로 작은수를 더해서 확인
            end_index--;
        }
    }

    cout << count;        
    
    return 0;
}