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. 참고





질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


+ Recent posts