코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.
참조 사이트: http://covenant.tistory.com/224
코딩테스트 대비를 위한 백준 문제 추천
코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고
covenant.tistory.com
Part 1 준비운동 - 일곱 난쟁이 (백준 2309)
문제 출처: https://www.acmicpc.net/problem/2309
2309번: 일곱 난쟁이
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
www.acmicpc.net
풀이
예전에 풀면서 다음에 다시 한번 풀어봐야 겠다고 생각해놨던 문제인데 이번에 다시 풀게 되었습니다.
그때나 지금이나 문제를 보자마자 무작위로 7개씩 조합해서 100이 되는지를 조사하면 되겠다고 접근하다가 갑자기
정신을 차리고(왜 그때랑 똑같이 삽질하는 거지...) 풀이를 생각해 냈습니다.
9명의 난쟁이중 7명의 키를 조합해서 100이 되는지를 검증하는 것 보다(반복문7개쓸건가??..)
9명 난쟁이의 키 총 합에서 두 명의 키를 뺀 값이 100이 될 때 그 두명을 제외시켜주는 것이 좋습니다.
단, 주의 해야할 점은 2중 반복문 안에서 두명을 검출하고 반복문을 탈출해야합니다.
2중 반복문으로 2명을 검출하고 break문을 걸어주지 않으면 101로 설정 해 둔 두 난쟁이의 키값이 또다른 100을 찾는 7명의 키조합 연산에 사용되어 7명이 구해지지 못하는 경우가 발생할 수도 있습니다.
실제로 아래 코드에서 24행과 28행을 주석처리하면 틀리게 됩니다.
코드
|
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
|
#include<iostream>
#include<algorithm>
using namespace std;
int arr[9];
int main()
{
int i,j, sum = 0;
for (int i = 0; i < 9; i++)
{
cin >> arr[i];
sum += arr[i];
}
//총합에서 2개의 난쟁이 키를 뺀 값이 100일 때 그 2명 제외
// 키가 100을 넘지않으므로 2개 검출 한 난쟁이의 키를 -1 or 101로 조절
for ( i = 0; i < 9; i++)
{
for ( j = 0; j < 9; j++)
{
if (i != j)
{
if (sum - arr[i] - arr[j] == 100)
{
arr[i] = 101, arr[j] = 101;
break;
}
}
}
if (arr[i] == 101 && arr[j] == 101)break;
}
sort(arr, arr + 9);
for (int i = 0; i < 7; i++)
cout << arr[i] << endl;
return 0;
}
|
cs |
|
|
|
결과
'문제풀이(BOJ)' 카테고리의 다른 글
| 코딩 테스트 준비 1단계 기본기 - 백준 2693 (0) | 2021.03.24 |
|---|---|
| 코딩 테스트 준비 1단계 기본기 - 백준 2609 (0) | 2021.03.24 |
| 코딩 테스트 준비 1단계 기본기 - 백준 10870 (0) | 2021.03.24 |
| 코딩 테스트 준비 1단계 기본기 - 백준 2460 (0) | 2021.03.23 |
| 코딩 테스트 준비 1단계 기본기 - 백준 10818 (0) | 2021.03.23 |