<링크>

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

+ Recent posts

티스토리툴바