백준 1940 주몽 (C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 1940 주몽 입니다

 

문제 해석

주몽 문제풀이 입니다

이 문제 같은경우는 우선 시간제한이 2초라서 조금 여유가 있습니다, 문제를 해석해보면

값옷을 만드는 재료들은 각각의 고유 번호를 가지고 있고, 두 재료의 고유 번호를 합해서 M이 되면 갑옷이 만들어 직 ㅔ됩니다

이때 N개의 재료와 M이 주어졌을때 값옷이 몇개가 만들어지는지를 구하면됩니다

 

예제를 보게되면 우선 재료의 개수 N은 6이 들어왔고, 갑옷을 만드는데 필요한수(고유한번호를 합친수) M은 9가 들어왔습니다

그리고 그다음줄에 N개의 재료들인 2 7 4 1 5 3 이 들어와있습니다 문제에서 두 재료의 고유번호를 합하라고 했으니

주어진 2 7 4 1 5 3 을 2개씩 조합을 해서 9가 될때 카운트를 하나  씩 세주면됩니다 즉 조합을 이용해서 풀면 쉽게 풀수있습니다

 

또한 이문제에 중요한 부분이있는데 바로 불필요한 연산을 하지 말아야 합니다 문제의 보면 고유한 번호는 10만보다 작거나 같은 자연수이다 라고 나와있습니다. 즉 고유한 번호는 10만이 최대이고 2개를 뽑을수있다고 했으니 20만이 최대값으로 잡힙니다 이때 20만 이후로는 계산을 할필요가 없으니 예외처리를 진행하여 불필요한 연산을 하지 않으면 속도 측면에서 이득을 볼수있습니다

 

문제 풀이 순서

1. 재료의 개수(N),갑옷을 만드는데 필요한수(M),정수 배열, 최종결과 변수를 선언합니다

2. N만큼 순회를 돌면서 배열에 값을 입력해줍니다

3. 이후 만약 M이 20만 이상이라면 0을 출력해줍니다

4. 아니라면 입력받은 배열에서 순서와 상관없이 숫자 2개를 뽑아줍니다

5. 뽑은 2개의 숫자가 M과 같다면 카운트를 해줍니다

6. 최종 카운트를 출력해줍니다

 

작성 코드

#include<bits/stdc++.h>
using namespace std;
int n,m,arr[15000],ret,temp;
int main(){
    cin >> n;
    cin >> m;

    for(int i = 0; i < n; i++){
        cin >> temp;
        arr[i] = temp;
    }
    if(m > 200000){
        cout << 0 << "\n";
    }else{
        for(int i =0; i < n;i++){
            for(int j = i +1; j < n; j++){
                if(arr[i] + arr[j] == m){
                    ret++;
                }
            }
        }
        cout << ret << "\n";
    }

    return 0;
}