백준 3040번 [백설 공주와 일곱 난쟁이](C++)-yes6686- 티스토리

백준 문제 풀이: 3040 [백설 공주와 일곱 난쟁이]

---

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

문제 설명:

아홉 난쟁이의 모자에 적힌 숫자가 주어질 때, 이 중 가짜 두 난쟁이를 찾아내고 나머지 일곱 난쟁이의 숫자를 출력하는 프로그램을 작성하세요.

입력 조건:

• 9개의 정수가 한 줄에 하나씩 주어집니다. 각 정수는 1 이상 99 이하입니다.
• 문제에서 항상 답이 유일한 경우만 입력으로 주어집니다.

출력 조건:

• 일곱 난쟁이의 숫자를 한 줄에 하나씩 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[9]; // 9명의 난쟁이 모자 숫자를 저장할 배열

int main() {
    int totalSum = 0;

    // 입력과 전체 합 계산
    for (int i = 0; i < 9; i++) {
        cin >> arr[i];
        totalSum += arr[i];
    }

    // 가짜 난쟁이 찾기
    int index1 = -1, index2 = -1;
    for (int i = 0; i < 8; i++) {
        for (int j = i + 1; j < 9; j++) {
            if (totalSum - (arr[i] + arr[j]) == 100) {
                index1 = i;
                index2 = j;
                break;
            }
        }
        if (index1 != -1) break; // 가짜 난쟁이를 찾았으면 루프 종료
    }

    // 진짜 난쟁이 출력
    for (int i = 0; i < 9; i++) {
        if (i != index1 && i != index2) {
            cout << arr[i] << '\n';
        }
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 아홉 난쟁이의 모자 숫자 중 두 가짜 난쟁이를 제외한 일곱 명의 숫자를 출력합니다.

• 전체 합 계산:
  • `totalSum`에 아홉 난쟁이 숫자의 합을 저장합니다.
• 가짜 난쟁이 찾기:
  • 이중 루프를 통해 두 난쟁이를 선택합니다.
  • `totalSum - (arr[i] + arr[j])`가 100인 경우, 두 난쟁이를 가짜로 판단합니다.
  • 가짜 난쟁이의 인덱스를 `index1`, `index2`에 저장하고 루프를 종료합니다.
• 출력:
  • 가짜 두 난쟁이의 인덱스를 제외하고 나머지 일곱 난쟁이의 숫자를 출력합니다.

시간 복잡도 분석:

• 입력: O(9).
• 이중 루프를 통한 탐색: O(9 × 8) ≈ O(81).
• 출력: O(9).

전체 시간 복잡도는 O(81), 즉 O(1)로 상수 시간 내에서 실행됩니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
20
7
23
19
10
15
25
8
13

출력:
7
8
10
13
19
20
23

위 입력에서는 두 가짜 난쟁이의 모자 숫자 합을 제외한 나머지 숫자가 출력됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!