문제 URL : www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
문제접근법 : 우리가 흔히 쓰는 리모컨을 생각하고 문제를 풀으셔야합니다. 그렇지만
숫자를 누르면서 +,- 버튼을 누르는 경우는 없잖아요? + -버튼을 누르는 순간 숫자를 누를수 없다고 생각하셔야합니다.
전 이걸 2가지 방법의 code를 보여드리겠습니다.
한가지는 bfs방법 다른한가지는 전체탐색
bfs방법으로 풀고 다른사람들은 어떻게 풀었는지 확인하다가 대부분 부르트 포스인 전체탐색으로 풀었더군요
시간은 전체탐색이 좀더 빠르더군요 그렇지만 다양한 방법이 있고 공부가 되셨으면합니다.
BFS코드:
|
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
//By 콩순이냉장고
#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
#define M 1000000
int n, m;
bool broken[10];
bool visit[M + 1];
struct rimocon{
int cur, flag, cnt;
rimocon(int cur, int flag, int cnt) :cur(cur), flag(flag), cnt(cnt){}
};
int bfs(){
queue<rimocon> q;
for (int i = 0; i < 10; i++){
if (broken[i])
continue;
q.push({ i, true, 1 });
visit[i] = 1;
}
while (!q.empty()){
int cur = q.front().cur;
int flag = q.front().flag;//숫자만 눌렀는지 확인하는버튼 +,-버튼누르게되면 숫자 못누름
int cnt = q.front().cnt;
q.pop();
if (cur == n)
return cnt;
if (flag){//숫자만 눌렀는지
for (int i = 0; i < 10; i++)
{
if (broken[i])
continue;
int next = cur * 10 + i;
if (0 <= next&&next <= M&&visit[next] == 0){
q.push({ next, true, cnt + 1 });
visit[next] = 1;
}
}
}
//+,-누르게됨
int next = cur + 1;
if (0 <= next&&next <= M&&visit[next] == 0){
q.push({ next, false, cnt + 1 });
visit[next] = 1;
}
next = cur - 1;
if (0 <= next&&next <= M&&visit[next] == 0){
q.push({ next, false, cnt + 1 });
visit[next] = 1;
}
}
return -1;//숫자 0~9까지 전부 못누르는 경우
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> m;
for (int i = 0; i < m; i++)
{
int c;
cin >> c;
broken[c] = 1;
}
int res = abs(n - 100);
int t = bfs();
if (t != -1){
res = min(res, t);
}
cout << res << "\n";
}
|
cs |
부르트포스 코드:
|
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
42
43
44
45
46
47
48
49
50
|
//By 콩순이냉장고
#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
#define M 1000000
int n, m;
bool broken[10];
int pressNum(int p){//아예 눌러서 이동할수있을때
int len = 0;
if (p == 0)
return !broken[0];
while (p){
if (broken[p % 10])
return 0;
len++;
p /= 10;
}
return len;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> m;
for (int i = 0; i < m; i++)
{
int t;
cin >> t;
broken[t] = 1;
}
int res = abs(n - 100);
for (int i = 0; i <= M; i++)
{
int num = pressNum(i);
if (num){//눌러서 이동할수없을경우 패스
res = min(res, abs(n - i) + num);//눌러서 이동할수있을경우 누른다음 나머지는 +,-로 이동해서 작은경우만
}
}
cout << res << "\n";
}
|
cs |
궁금한점 혹은 모르는점 혹은 논리적으로 오류가 있는점 있다면 어제든지 댓글 이용부탁드립니다. ㅎㅎ
'백준' 카테고리의 다른 글
| 백준 12931 두 배 더하기 (0) | 2020.12.31 |
|---|---|
| 백준 16953 A → B (2) | 2020.12.27 |
| 백준 16562 친구비 (0) | 2020.10.02 |
| 백준 10216 Count Circle Groups (0) | 2020.10.02 |
| 백준 5373 큐빙(SW 역량 테스트 기출 문제) (0) | 2020.09.21 |
