[백준] 1940번 - 주몽 c++

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

 

문제 설명

• 각각의 재료는 고유한 번호를 가진다.
• 두 개의 재료로 하나의 갑옷을 (두 재료의 합이 고유번호 m) 만드는데 몇 개나 만들 수 있는지 구한다.

풀이 방법

재료가 15000개가 있으므로 모든 조합을 확인할 경우 매우 오래걸린다.

15000C2 =  약 1억 1000으로 매우 비효율적이다.

정렬이 필요하지 않고 검색을 빠르게 하는 게 최우선 이므로 자료구조 hashmap을 사용한다.

이경우 find에서 O(1)이 시간이 걸리므로 시간복잡도를 O(n)으로 줄일 수 있다.

풀이 코드

#include <iostream>
#include <unordered_map>

using namespace std;
int n,k,num,answer;
int main() {
    unordered_map<int,int> weapon;
    cin >> n >> k;
    
    for(int i=0; i<n; i++){
        cin >> num;
        if(weapon.find(k-num) != weapon.end()){
            answer += weapon[k-num];
        }
        weapon[num]++;
    }
    
    cout << answer <<'\n';
    
    return 0;
}

papago is broken