BOJ::1463 1로만들기

https://www.acmicpc.net/problem/1463


문제를 보고

d[n]=min(d[3*n]+1, [2*n]+1, d[n+1]+1) 라는 식을 세워 n을 1씩 줄이면서 하는걸 생각했다.


마찬가지로 초기값을 d[1]=1, d[2]=1, d[3]=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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main{
 
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int d[]=new int[1000001];
        
        while(n>=1){
            if(n%3 == 0){
                if(d[n/3]==0 || d[n/3]>d[n]+1){
                    d[n/3]=d[n]+1;
                }
            }
            if(n%2 == 0){
                if(d[n/2]==0 || d[n/2]>d[n]+1){
                    d[n/2]=d[n]+1;
                }
            }
            if(d[n-1]==0 || d[n-1]>d[n]+1){
                d[n-1]=d[n]+1;
            }
            n--;
        }
        System.out.println(d[1]);
    }
}
 
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main{
 
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int d[]=new int[n+1];
        d[1]=1;
        if(n>1){
            d[2]=1;
        }
        if(n>2){
            d[3]=1;
        }
        
        for(int i = 4 ; i <= n ; i++){
            d[i]=d[i-1]+1;
            if(i%2==0){
                if(d[i]>d[i/2]+1){
                    d[i]=d[i/2]+1;
                }
            }
            if(i%3==0){
                if(d[i]>d[i/3]+1){
                    d[i]=d[i/3]+1;
                }
            }
        }
        System.out.println(d[n]);
    }
    
}
 
cs



저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

1697 숨바꼭질  (0) 2017.12.31
1475 방 번호  (0) 2017.12.31
1389 케빈 베이컨의 6단계 법칙  (0) 2017.12.31
1325 효율적인 해킹  (0) 2017.12.31
1309 동물원  (0) 2017.12.31

+ Recent posts

티스토리툴바