<링크>
https://www.acmicpc.net/problem/1107
지금으로부터 6달 전, 2018년 1월 5일에 풀었었는데 이 때에 비해 실력이 얼마나 늘었는지 궁금해서
똑같은 문제를 또 봤다. 많이 틀리고 개고생했던 기억이 난다.
<2018.01.15 소스코드>
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 85 86 87 | import java.util.Collection; import java.util.Collections; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { // 61453 // 7 8 9 Scanner in = new Scanner(System.in); String num = in.next(); int channel = Integer.parseInt(num); int K = in.nextInt(); LinkedList<Integer> list = new LinkedList<Integer>(); for (int i = 0; i < 10; ++i) list.add(i); for (int i = 0; i < K; ++i) list.remove(new Integer(in.nextInt())); // list정렬 Collections.sort(list); int nogada = Math.abs(channel - 100); if (K == 10) { // 칠수있는 번호가 하나도없을시 (다고장) System.out.println(Math.abs(channel - 100)); return; } int mini = channel; String min = null; boolean check1 = false,check2=false; while (mini >= 0) { min=Integer.toString(mini); if(channel-mini+min.length()>=nogada) break; check1 = true; // 성공했다고 가정 for (int j = 0; j < min.length(); ++j) { int n = min.charAt(j) - '0'; if (list.indexOf(n) == -1) { check1 = false; break; } // 실패 } if (check1 == true) break; else --mini; } int maxi=channel; String max; while (true) { max=Integer.toString(maxi); if(maxi-channel+max.length()>=nogada) break; check2 = true; // 성공했다고 가정 for (int j = 0; j < max.length(); ++j) { int n = max.charAt(j) - '0'; if (list.indexOf(n) == -1) { check2 = false; break; } // 실패 } if (check2 == true) break; else ++maxi; } mini=channel-mini+min.length(); maxi=maxi-channel+max.length(); int result=nogada; if(maxi<result && check2){ result=maxi; } if(mini<result && check1){ result=mini; } System.out.println(result); // 만들수있는숫자 i가 나옴 } } | cs |
<풀이>
뭐저렇게 복잡해보이는지 잘 모르겠다. 꼴보기 싫어서 그냥 새로 풀었다.
<2018.07.26 소스코드-1>
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 | #include<stdio.h> #include<vector> #include<math.h> using namespace std; vector<int> v; int seq[6]; int X[10]; int ans, N, M; void check(); void dfs(int); int main() { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { int n; scanf("%d", &n); X[n] = 1; // 1고장난애들 } ans = abs(N - 100); v.push_back(0); //0은 무조건 추가, 자리수관리용 for (int i = 1; i < 10; ++i) if (!X[i]) v.push_back(i); //누를수있는 버튼을 벡터에 추가 dfs(0); printf("%d",ans); } void dfs(int len) { if (len == 6) { check(); return; } for (int i = 0; i < v.size(); ++i) { seq[len] = v[i]; dfs(len + 1); } } void check() { int i = 0; int cnt = 6; while (i < 5 && seq[i] == 0) //앞에 붙은 0들을 제거 { ++i; --cnt; } int channel = 0; while(i<6) { if (seq[i] == 0 && X[0]) //앞의 0을 다 제거했으므로 이제 사이에 나오는 0은 0버튼이 고장났는지 여부에 따라 갈림 return; channel += seq[i] * pow(10, 5 - i); ++i; } if (abs(N - channel) + cnt < ans) ans = abs(N - channel) + cnt; } | cs |
리모콘 버튼을 하나 선택하고 다음자리 수를 재귀를 돌렸다. 최대 6자리까지만 했다.
N의 최대입력값이 500000이기 때문에 999900 이상되는 수부터는 +,-를 이용해서 오는건, 100번에서 +,-만 이용해서 오는 것보다 구리기 때문이다.
시간복잡도는 10^6이다.
맨 처음 채널에 100이기 때문에 100에서부터 원하는 채널 N까지 +,-를 이용해 가는 값, 즉 |N-100| 으로 최솟값을 일단 정해놓고 고장이 안난 버튼으로 재귀를 돌다가 depth가 6이 되면 최솟값을 갱신했다.
예를 들어
고장난 번호가 3,4,5,6,7,8,9 일 때 가능한 번호는 0,1,2이고
000000
000001
000002
...
000012
...
222220
...
222222
이렇게 모두 체크해본다.
000012를 체크하면, 앞의 0은 누른 횟수로 치지않고 2번 누른 것으로 한다.
근데 여기서 0 버튼이 고장나면 문제가 발생한다.
고장이 안난 버튼으로만 재귀를 돌렸기 때문에
111111
111112
...
222222 이렇게 체크하게 되는데
그럼 6자리가 아닌 채널들은 체크를 못하게된다.
그래서 0은 무조건 재귀돌릴 때 추가하고, 체크할 때 걸러내게끔 했다
000012 -> 얘는 앞자리채우기로써 0이 들어온거니까 : ㅇㅋ
011012 -> 중간에 유효숫자로써 0이 들어온거니까 : ㄴㄴ
<2018.07.26 소스코드-3>
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 | #include<stdio.h> #include<algorithm> #include<math.h> #include<string> int check(int); using namespace std; int X[10]; int ans, N, M; int main() { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { int n; scanf("%d", &n); X[n] = 1; //고장난애들 } ans = abs(100 - N); for (int i = 0; i <= 1000000; ++i) { int len = check(i); if (len) ans = min(abs(N - i) + len, ans); } printf("%d", ans); } int check(int num) { string s=to_string(num); int len = s.length(); for (int i = 0; i < len; ++i) { if (X[s[i] - '0']) return 0; } return len; } | cs |
<풀이>
새롭게 재귀로 풀고나서 좀 늘었구나 싶었는데
다른 사람들의 소스코드를 살펴보고나서 깨달음을 얻었다.
그냥 0번부터 100000번까지 for문으로 쫙 돌려보며
가능한 숫자버튼으로 만들수 있는 채널이면 최솟값을 갱신시키는 방식이다.
코드가 80->60->40 줄로 짧아져서 기쁘긴한데 난 아직 멀었다.
'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글
| 백준 15686 치킨배달 (0) | 2018.09.30 |
|---|---|
| KOITP 고장난시계 (0) | 2018.07.23 |
| 백준 1421 나무꾼 이다솜 ::들짐승 (0) | 2018.07.22 |
| 백준 14888 연산자 끼워넣기 :: 들짐승 (0) | 2018.07.22 |
