[백준 3040] 백설 공주와 일곱 난쟁이 (C#, C++) - soo:bak
작성일 :
문제 링크
설명
아홉 난쟁이의 키 중에서 합이 정확히 100이 되는 일곱 명을 찾아 출력하는 문제입니다.
- 아홉 개의 자연수가 주어지며, 이 중 두 개는 가짜 난쟁이의 키입니다.
- 나머지 일곱 개의 수의 합이 정확히
100
이 되도록 하는 조합을 찾아야 합니다. - 조건에 맞는 일곱 난쟁이의 키를 입력 순서를 유지한 채 출력해야 합니다.
접근법
- 전체 키의 총합을 구한 뒤, 그 합에서
100
을 뺀 값을 저장해둡니다. - 아홉 명 중 두 명을 골라, 그 두 키의 합이 위에서 계산한 값과 같다면 해당 두 명이 가짜 난쟁이입니다.
- 조건을 만족하는 두 명을 제외한 나머지 일곱 명을 입력 순서대로 출력하면 됩니다.
Code
[ C# ]
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
using System;
using System.Collections.Generic;
class Program {
static void Main() {
var dwarfs = new List<int>();
int total = 0;
for (int i = 0; i < 9; i++) {
int h = int.Parse(Console.ReadLine());
dwarfs.Add(h);
total += h;
}
int excess = total - 100;
int skip1 = -1, skip2 = -1;
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 9; j++) {
if (dwarfs[i] + dwarfs[j] == excess) {
skip1 = i;
skip2 = j;
break;
}
}
if (skip1 != -1) break;
}
for (int i = 0; i < 9; i++) {
if (i != skip1 && i != skip2)
Console.WriteLine(dwarfs[i]);
}
}
}
[ C++ ]
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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vi dwarfs(9);
int total = 0;
for (int i = 0; i < 9; i++) {
cin >> dwarfs[i];
total += dwarfs[i];
}
int excess = total - 100;
int fake1 = -1, fake2 = -1;
bool found = false;
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 9; j++) {
if (dwarfs[i] + dwarfs[j] == excess) {
fake1 = i;
fake2 = j;
found = true;
break;
}
}
if (found) break;
}
for (int i = 0; i < 9; i++) {
if (i != fake1 && i != fake2)
cout << dwarfs[i] << "\n";
}
return 0;
}