백준 알고리즘(C++)

백준 1940번 주몽( C++ )

coding232624 2024. 3. 4. 23:30

문제

https://www.acmicpc.net/problem/1940

 

1940번: 주몽

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고

www.acmicpc.net

 

해설

2개를 합쳐 원하는 수를 뽑는 경우이기 때문에 정렬 후 비교

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
 
int N,M,ret,cnt1,tmp;
int N_list[15004];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin >> N >> M;
    cnt1 = N-1;
    
    for(int i =0; i<N;i++){
        cin >> tmp;
        N_list[i] = tmp;
    }
    
    sort(N_list,N_list+N);
 
 
    
    for(int i = 0; i <N;i++){
        if (N_list[i] > M) break;
        if(i >= cnt1) break;
        for(int cnt = cnt1 ;cnt > i; cnt--){
            if (N_list[i]+N_list[cnt] == M){
                ret++;
                
                cnt1 = cnt-1;
                break;
            }
            else if(N_list[i]+N_list[cnt] < M){
                cnt1 = cnt;
                break;
            }
        }
        
    }
    cout << ret;
    return 0;
}
cs