[PS] 백준 1940 주몽

이번에는 백준 1940번 주몽 문제를 풀어보았습니다.

이 문제는 주어진 재료 번호들 중에서 두 개를 골랐을 때, 그 합이 M이 되는 경우가 몇 개인지를 구하는 문제입니다.

결국 핵심은 N개의 수 중 두 수를 고르는 경우를 확인하는 것이었습니다.

문제 설명

갑옷은 두 개의 재료로 만들 수 있고,

두 재료 번호의 합이 M이 되면 갑옷 하나를 만들 수 있습니다.

입력으로는

• 재료의 개수 N
• 필요한 합 M
• 재료 번호들

이 주어지고,

이 중 두 재료를 골라 합이 M이 되는 경우의 수를 출력하면 됩니다.

---

풀이 아이디어

이 문제는 결국 N개의 수 중 2개를 선택했을 때 합이 M이 되는지 확인하는 문제입니다.

노션에서는 두 가지 방식으로 정리해두었습니다.

• 이중 for문을 사용하는 방식
• 재귀를 사용하는 방식

두 방식 모두 결국은 두 수를 고르는 조합을 확인하고 있습니다.

---

1. 이중 for문을 사용한 풀이 (V1)

가장 먼저 생각할 수 있는 방식은 모든 두 수 쌍을 직접 확인하는 것입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;

    int n;
    cin >> n;

    vector<int> v;
    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (v[i] + v[j] == n) {
                cnt++;
            }
        }
    }

    cout << cnt << "\n";
    return 0;
}

풀이 흐름

1. 재료 개수 N과 목표 합 M을 입력받는다.
2. 재료 번호들을 벡터에 저장한다.
3. i, j 두 인덱스를 사용해 가능한 모든 두 수 쌍을 확인한다.
4. 두 수의 합이 M이면 카운트를 증가시킨다.
5. 최종 결과를 출력한다.

이 방식은 가장 단순하고 구현도 직관적입니다.

---

2. 재귀를 사용한 풀이 (V2)

두 번째 방식은 재귀를 사용해서 두 수를 선택하는 방식입니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
vector<int> choose;
int cnt;
int N;
int n;

void solve(int start) {
    if (choose.size() == 2) {
        if (choose[0] + choose[1] == n)
            cnt++;
        return;
    }

    for (int i = start; i < N; i++) {
        choose.push_back(v[i]);
        solve(i + 1);
        choose.pop_back();
    }
}

int main() {
    cin >> N;
    cin >> n;

    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    solve(0);

    cout << cnt << "\n";
    return 0;
}

풀이 흐름

1. 재료 번호들을 벡터에 저장한다.
2. 재귀를 사용해 두 개의 수를 선택한다.
3. 두 수를 모두 선택했을 때 합이 M인지 확인한다.
4. 조건을 만족하면 카운트를 증가시킨다.
5. 모든 조합을 확인한 뒤 결과를 출력한다.

---

구현 포인트

1. 결국 두 수를 고르는 조합 문제

두 코드 모두 방식은 다르지만,

결국은 N개의 수 중 두 가지 수를 고르는 조합을 확인하는 풀이입니다.

• 이중 for문은 반복문으로 조합을 확인하는 방식이고
• 재귀는 선택 과정을 함수 호출로 구현한 방식입니다

즉, 구현 방식만 다를 뿐 핵심은 같습니다.

---

2. 중복 없이 두 수를 고르기

이 문제에서는 같은 두 수 쌍을 중복으로 세면 안 됩니다.

그래서 이중 for문에서는

for (int j = i + 1; j < N; j++)

처럼 j를 i+1부터 시작하게 해서 중복을 막았습니다.

재귀 방식에서도 start 인덱스를 사용해서

이미 선택한 이전 원소보다 뒤쪽 원소들만 선택하도록 했습니다.

---