https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
www.acmicpc.net
두가지 방법으로 풀이를 했는데 하나는 재귀를 이용한방법
하나는 0부터 1000000까지 확인하는 방법을 사용했습니다.
|
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
83
84
|
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
#define MSIZE 10
using namespace std;
string N;
int M;
char breakButton[MSIZE];
string Button = { '0','1','2','3','4','5','6','7','8','9'};
int chk[500001];
int pluschk=1;
int minuschk=1;
int mmin = 0x7fffffff;
struct Data {
string num;
int cnt;
};
void init() {
cin >> N;
cin >> M;
for (int i = 0; i < M; i++) {
cin >> breakButton[i];
if (breakButton[i] == '-') {minuschk = 0; }
if (breakButton[i] == '+') { pluschk = 0; }
}
for(int i=0;i<M;i++)
for (int j = 0; j <=Button.size(); j++) {
if (Button.size()!=0&&breakButton[i] == Button[j])
}
}
void dfs(int idx,string num) {
if (idx > N.size()+1)return;
if (idx <= N.size()+1&&num.size()!=0) {
//cout << num << endl;
int n = stoi(N);
int a = stoi(num);
if (n >=a&&pluschk) {
if (mmin > idx + (n - a)) mmin = idx + (n - a);
}
if(n<=a&&minuschk){
if (mmin > idx + (a - n))mmin = idx + (a - n);
}
}
for (int i = 0; i < Button.size(); i++) {
num.push_back(Button[i]);
dfs(idx + 1,num);
num.pop_back();
}
}
string a;
int main(void) {
init();
if (N == "100") {
cout << 0 << endl;
return 0;
}
int n = stoi(N);
int b = 100;
if (n >= b && pluschk) {
if (mmin > (n-b))mmin = (n-b);
}
if (n <= b && minuschk) {
if (mmin > (b-n))mmin = (b-n);
}
dfs(0,a);
/*if (Button[0] == '0'&&Button.size()==1) {
b = 0;
if (n >= b && pluschk) {
if (mmin > (n - b)+1)mmin = (n - b)+1;
}
if (n <= b && minuschk) {
if (mmin > (b - n)+1)mmin = (b - n)+1;
}
}
*/
cout << mmin << endl;
return 0;
}
|
재귀의 경우는 간단하게 고장난 번호를 따 제외 시키고 있는 번호로 만들수 있는 모든 경우의 번호를 만들고 그것의
차가 + ,- 버튼을 누른것이므로 그것의 최소를 출력하는 식으로 풀이를 했습니다.
이방법이 뭔가 복잡하지만 처음 문제를 접했을때는 다른 방안이 생각나지 않더라구요 그래서 이렇게 풀었고,
그리고 여기서 정말 중요한것은 원래 채널의 위치가 100 이기때문에 100에 대해서 우선적으로 타겟위치와의 버튼
누르는 회수가 짧을 수 있기때문에 그경우를 처음에 해주고 재귀를 돌려주시면됩니다.
그리고 완전 다 검색하면서 그 숫자가 버튼을 누를 수 없는 번호라면 제외 시켜주는 방식은
|
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
|
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int N;
int M;
int chk[10];
int size10[] = { 10,100,1000,10000,100000,1000000,1000000 };
int Min = 0x7fffffff;
void init() {
cin >> N;
cin >> M;
for (int i = 0; i < M; i++) {
int num;
cin >> num;
chk[num] = 1;
}
}
bool chknum(int num) {
string n1;
n1 = to_string(num);
for (int i = 0; i <10; i++) {
if (chk[i] == 1) {
return false;
}
}
}
return true;
}
int main(void)
{
init();
if (N == 100) {
cout << 0 << endl;
return 0;
}
Min=Min > abs(N - 100) ? abs(N - 100): Min;
string sizeN = to_string(N);
for (int i = 0; i <= 1000000; i++) {
if (chknum(i)) {
string a =to_string(i);
Min = Min > a.size()+abs(N - i) ? a.size()+abs(N - i) : Min;
}
}
cout << Min << endl;
return 0;
}
|
좀 이게 소스를 넣어보면 느리게 동작하는게 stl로 인트를 문자열로 바꾸고 하는식을 사용해서 함수를 넣나들어
조금 느립니다. 물론 그렇게 안하고도 가능하지만 방식은 진짜 간단하게 처음부터 누를수 있는 숫자를 다 눌러보자
입니다. 진짜 완전탐색이죠? 그 숫자를 하면서 chknum 함수를 통해 걸러주고 그 차이의 최소를 출력해주는 방식입니다.
진짜 예전에는 풀시도조차 포기하게 만드는 문제였는데 이제 조금은 실력이 올랐나보네요 . 물론 문제가 엄청 어려운
문제가 아니라서 그랬을수 도 있지만 제나름 성장하고 있음을 느꼈던 문제였습니다.
같은 문제라도 다른 풀이방식이 존재하지만 항상 알고리즘은 정확하고 빠른 방법으로 풀어야 합니다. 여러분은
저보다 더 잘하시니까 아실꺼라 생각합니다. 오늘은 여기까지 입니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2234 성곽 (0) | 2019.10.07 |
|---|---|
| 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 (0) | 2019.10.07 |
| 백준 3019 테트리스 (0) | 2019.10.04 |
| 백준 3568 iSharp (0) | 2019.10.04 |
| 백준 14226 이모티콘 (0) | 2019.10.03 |
댓글