BAEKJOON_1107) 리모컨

1107) 리모컨 (19.10.03)






* 이동하고자 하는 채널보다 큰 수에서 내려올 수도 있기 때문에, 1000000까지로 i를 잡고,
* i를 누를 수 있는지 확인(sol() 함수) 하고, 되면 그 숫자에서 원하는 곳까지 이동거리 확인.
* leng의 값(누른 숫자의 길이)과 두 수의 차이(+/- 눌러야 하는 횟수)를 더해준다.
* 기존 채널인 100에서 +/-로 갈 수 있는 것과 비교해서 더 적게 버튼을 누르는 것을 출력.

* 브루트 포스 vs 다이나믹
* 두 가지 모두 전체 탐색인줄 알았는데
* 브루트 포스는 선택에 따라서 뒷부분을 다 조사해야하고,
* 다이나믹은 구하는 값(최대, 최소) 말고는 의미가 없다고 한다.

* 다이나믹 문제는 브루트 포스로 풀 수 있지만,
* 모든 브루트 포스 문제를 다이나믹으로 풀 수있는 것은 아니다.

* 아래 코드는 처음에 풀었던 코드.
* 100에서 이동 / n보다 큰 채널에서 이동 / n보다 작은 채널에서 이동
* 이렇게 세 가지 경우를 돌려줬다.
* n이 최대값인 500000으로 테스트하면 값이 출력되지 않았다.
* 숫자를 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.util.*;
import java.io.*;

class Main{
    public static boolean[] ch = new boolean[10];
    public static int N;
    public static int nn;
    public static int ans;
    public static void nto100(int n1) {
        //System.out.println("nn : "+ nn + "  N+ans : " +  (N+ans) + "  n1 : " + n1 + " \n");
        if(nn>=N+ans) return;
        int ni = n1%10;
        //System.out.println("ni : " + ni +  " \n");
        if(ch[ni]==true) {
            nn = nn+1;
            nto100(nn);
        }
        else {
            n1 = n1/10;
            if(n1<=0) return;
            nto100(n1);
        }
    }
    public static void oton(int n2) {
        if(nn<=0 || nn<=N-ans) return;
        //System.out.println("nn : " + nn +"   n2 : " + n2 + " \n");
        int ni = n2%10;
        //System.out.println("ni : " + ni +" \n");
        if(ch[ni]==true) {
            nn = nn-1;
            oton(nn);
        }
        else {
            n2 = n2/10;
            if(n2<=0) return;
            oton(n2);
        }
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer tk = new StringTokenizer(br.readLine());
        
        String n = tk.nextToken(); 
        N = Integer.parseInt(n);
        int m = Integer.parseInt(br.readLine());
        if(m>0) tk = new StringTokenizer(br.readLine());
        for(int i=0;i<m;i++) {
            int a = Integer.parseInt(tk.nextToken());
            ch[a] = true;
        }
        
        //더하기/빼기 누르는 횟수
        ans = Math.abs(Integer.parseInt(n)-100);
        
        bw.write("100에서 더하기/빼기 : " + String.valueOf(ans));
        bw.write("\n=============================\n");
       
        nn = Integer.parseInt(n);
        
        int leng = 1;
        int a = 0;
        nto100(nn);
        bw.write("nto100 :" + nn + " \n");
        
        if(nn>0) leng = (int)Math.log10(nn)+1;
        else if(nn==0) leng = 1;
        
        a = Math.abs(Integer.parseInt(n)-nn);
        a = a+Math.min(leng, Math.abs(nn-100));
        bw.write("a :" + a+ " \n");
        ans = Math.min(ans, a);
        bw.write("n보다 큰 수에서 n으로 : "+ a + " \n");
        bw.write("\n=============================\n");
        
        nn = Integer.parseInt(n);
        oton(nn);
        bw.write("oton :" + nn + " \n");
        
        if(nn>0) leng = (int)Math.log10(nn)+1;
        else leng = ans;
        
        a = Math.abs(nn-Integer.parseInt(n));
        a = a+Math.min(leng, Math.abs(nn-100));
        bw.write("n보다 작은 수에서 n으로 : "+ a + " \n");
     
        ans = Math.min(ans, a);
        bw.write("answer: " + ans + " \n");
        bw.flush();
        bw.close();

    }
}
cs

댓글

댓글 쓰기

이 블로그의 인기 게시물