문제
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
출처
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 1번
- 데이터를 추가한 사람: ung27540421
- 어색한 표현을 찾은 사람: upple1
알고리즘 분류
일단 틀린 코드 먼저 공개합니다. 왜 틀렸는지를 알아야 다음부터 안 틀릴테니까요!
#include<stdio.h>
#define swap(a,b) { int t = a; a = b; b = t;}
int main(){
int arr[9];
for(int i = 0 ; i < 9 ; i++){
scanf("%d",&arr[i]);
}
int end = 0;
while(end!=7){
if(arr[end] > arr[end+1]){
swap(arr[end],arr[end+1]);
end = 0;
}else
end++;
}
for(int i = 0 ; i < 7 ; i++){
printf("%d\n",arr[i]);
}
}이제 아래는 정답 코드입니다. 코드의 길이가 상당히 많이 늘어났네요. 여러가지 조건들을 빼먹고 코드를 작성한게 보입니다.
#include<stdio.h>
#include<string.h>
#define swap(a,b) { int t = a; a = b; b = t;}
int main(){
int arr[9];
int h = 0;
int res = 0;
for(int i = 0 ; i < 9 ; i++){
scanf("%d",&arr[i]);
h+=arr[i];
}
int end = 0;
while(end!=8){
if(arr[end] > arr[end+1]){
swap(arr[end],arr[end+1]);
end = 0;
}else
end++;
}
int h100 = h - 100;
int a,b;
for(int i = 0 ; i <9 ; i++){
for(int j = i+1 ; j < 9 ; j++){
if(h100==arr[i]+arr[j]){
a = i;
b = j;
break;
}
}
}
for(int i = 0 ; i < 9 ; i++){
if(i != a && i !=b)
printf("%d\n",arr[i]);
}
}브루트포스 알고리즘은 그리드 알고리즘과 거의 맞먹는 친구인데요. 전수조사, 전체 탐색하는 알고리즘이기때문에 굉장히 효율이 좋지 않습니다. 하지만, 알고리즘을 잘 작성한다면 무조건 정답을 찾는 방법이기 때문에 알아둬서 나쁠 것은 없는 알고리즘입니다. 특히, 최근에는 1번 이나 2번으로 코딩 테스트에 자주 등장하기 때문에 쉬운 문제에 속하는데요. 문제의 유형을 알고 어떤 형태의 알고리즘을 작성해야되는지 알고 시험에 응시하는 것이 중요하기 때문에 브루투포스 알고리즘은 일단 다 풀어보고 시험에 응시해야될 필요성이 있습니다!
