728x90
0. [c++] 백준 - |
https://www.acmicpc.net/problem/1107
1. 풀이 |
1) 처음엔 리모컨을 누르는 것을 완전히 구현한 뒤, (누른 숫자) - (찾는 숫자)를 하여 +,-를 하는 횟수를 카운트 할 생각이었었다.
찾는 번호를 누를 수 없는 경우에는, 위에서 가장 근접한 값, 아래에서 가장 근접한 값을 찾은 뒤, 그 숫자들의 차이를 찾고, 이것 저것해서 누르는 횟수가 가장 작은 값을 반환하는 방식을 구현 하였었는데,
이 구현이 너무 더럽게 힘들어서 다른 방법을 찾아보았다.
2) 다음 방법으로는 무식하게 풀기(brute force)를 활용하여보았다.
애초에 찾는 범위가 1억을 넘지 않으므로, 이 구현을 1번씩 한다해서 시간초과를 하지 않는 것을 알 수 있다.
따라서 이러한 구현을 통해 문제를 풀게 되었다.
2. 소스코드 |
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 | #include<iostream> #include<string> #include<stdlib.h> //abs를 활용하기 위해서 using namespace std; int INF = 1000007; int broken[10]; int Min(int a, int b) { return a < b ? a : b; } bool possible(int k) { if (k == 0) return broken[0] ? false : true; while (k) { if (broken[k % 10] == 1) { return false; } k /= 10; } return true; } int find(int N) { int hundred = abs(N - 100); int button_min = INF; int temp; for (int i = 0; i <= INF; i++) { if (possible(i)) { //버튼을 누른 횟수 temp = to_string(i).length(); //+,-를 해야하는 횟수 temp += abs(i - N); //만일 이번 계산이 최소였다면, 저장하자. button_min = Min(button_min, temp); } } //가장 횟수가 적은 방법을 반환. return Min(hundred, button_min); } int main(void) { int N, M, temp; cin >> N >> M; for (int i = 0; i < M; i++) { cin >> temp; broken[temp] = 1; } cout << find(N) << endl; return 0; } | 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 51 52 | #include<iostream> #include<string> #include<algorithm> using namespace std; int broken[10]; bool possible(int k) { if (k == 0) return broken[0] ? false : true; while (k) { if (broken[k % 10] == 1) { return false; } k /= 10; } return true; } int find(const int& N) { int ret = abs(N - 100); int temp; int INF = N * 2 - 100; if (INF < 100) INF = 100; //0 ~ (N*2 - 100)의 범위의 번호를 리모컨으로 누르는 경우의 값을 구하자. for (int i = 0; i <= INF; i++) { //버튼을 누른 횟수 temp = to_string(i).length() + abs(i-N); if (possible(i)) { //만일 이번 계산이 최소였다면, 저장하자. ret = min(temp, ret); } } return ret; } int main(void) { int N, M, temp; cin >> N >> M; for (int i = 0; i < M; i++) { cin >> temp; broken[temp] = 1; } cout << find(N) << endl; return 0; } | 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<iostream> #include<string> #include<algorithm> using namespace std; int INF = 1000007; int broken[10]; int N, M; bool possible(int k) { if (k == 0) return broken[0] ? false : true; while (k) { if (broken[k % 10] == 1) { return false; } k /= 10; } return true; } int find() { int ret = abs(N - 100); int temp; int inf = N * 2 - 100; if (inf < 100) inf = 100; //기저 사례 : 모든 버튼이 존재하지 않는 경우 if (M == 10) return ret; //N보다 더 큰 수로 버튼 이동 for (int i = N; i <= inf; i++) { //버튼을 누른 횟수 temp = to_string(i).length() + abs(i - N); if (possible(i)) { //한번이라도 이동을 하면 바로 탐색을 종료한다. ret = min(temp, ret); break; } } for (int i = N; i >= 0; i--) { //버튼을 누른 횟수 temp = to_string(i).length() + abs(i - N); if (possible(i)) { //한번이라도 이동을 하면 바로 탐색을 종료한다. ret = min(temp, ret); break; } } return ret; } int main(void) { int temp; cin >> N >> M; for (int i = 0; i < M; i++) { cin >> temp; broken[temp] = 1; } cout << find() << endl; return 0; } | cs |
3. 참고 |
질문이나 지적 있으시면 댓글로 남겨주세요~
도움 되셨으면 하트 꾹!
'<백준> > |C++| hard' 카테고리의 다른 글
[c++] 백준 6549 - 히스토그램에서 가장 큰 직사각형 (0) | 2019.04.27 |
---|---|
[c++] 백준 1780 - 종이의 개수(string의 치환, 공백 포함 입력(getline), replaceall, erase, remove, string활용 전체적으로) (0) | 2019.04.25 |
[c++] 백준 2981 - 검문 (0) | 2019.04.17 |
[c++] 백준 1022 - 소용돌이 예쁘게 출력하기 (0) | 2019.04.16 |
[C++] 백준 11066 - 파일 합치기(동적 계획법, 이후에 다시 보자) (0) | 2019.04.16 |