백준 1940번 [주몽](C++) -yes6686- 티스토리

백준 문제 풀이: 1940번 [주몽]

---

문제 링크: https://www.acmicpc.net/problem/1940

문제 설명:

주어진 재료들의 번호를 이용해 두 재료의 번호 합이 특정 숫자 M이 되는 경우의 수를 구하는 문제입니다. 재료 번호는 정수로 주어지며, 각 재료를 하나씩만 사용할 수 있습니다.

---

문제 해결 코드

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

int arr[15001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n; // 재료의 개수
    cin >> n;
    int m; // 목표 숫자
    cin >> m;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr, arr + n); // 배열을 정렬
    
    int ans = 0; // 가능한 경우의 수
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] > m) break; // 합이 목표 숫자를 넘으면 종료
            if (arr[i] + arr[j] == m) {
                ans++;
            }
        }
    }
    
    cout << ans << '\n'; // 결과 출력
}

---

코드 설명

위 코드는 모든 두 재료 쌍을 탐색하여 그 합이 M이 되는 경우의 수를 계산합니다. 주요 로직은 다음과 같습니다:

1. 입력 처리: 재료의 개수와 목표 숫자 M을 입력받은 뒤, 재료 번호를 배열에 저장합니다.
2. 정렬: 배열을 정렬하여 효율적인 탐색이 가능하도록 합니다.
3. 브루트포스 탐색: 모든 두 재료 쌍을 확인하여 합이 M이 되는 경우를 카운트합니다.

시간 복잡도:

• 정렬: O(N log N)
• 중첩 반복문: O(N²)

따라서 전체 복잡도는 O(N log N + N²)입니다. 하지만 최적화를 통해 더 효율적인 풀이를 작성할 수 있습니다.

---

결과

위 코드는 문제를 해결하며, 입력에 따라 정확히 가능한 경우의 수를 출력합니다. 추가적인 최적화를 통해 성능을 개선하거나 다른 접근 방식을 제안하고 싶다면 댓글로 공유 부탁드립니다!