반응형
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
반례 모음 www.acmicpc.net/board/view/46120
글 읽기 - [반례모음]
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
|
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
40
41
|
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, m, now = 100, ans = 987654321;
int button[11];
void func(int num, int cnt) {
// main에서 처음 넘겨주는 num이 0이므로
// 숫자를 하나도 추가하지 않았을 때(cnt==0)는 검사 안함
// 처리 안해주면 반례 발생
if(cnt > 0)
ans = min(ans, abs(n-num) + cnt);
// 종료 조건
if (cnt == 6) {
return;
}
// 백트래킹으로 숫자 증가
for (int i = 0; i < 10; i++) {
if (button[i]) {
num = num * 10 + i;
func(num, cnt +1);
num = num - i;
num /= 10;
}
}
}
int main() {
memset(button, 1, sizeof(button));
cin >> n >> m;
rep(i, m) {
int x;
cin >> x;
button[x] = 0;
}
ans = abs(n - 100);
func(0, 0);
cout << ans;
}
|
cs |
반응형