[java] 백준 1463 : 1로 만들기

문제

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

1463번: 1로 만들기

유형: dp

 

 

풀이

D[i] 는 i에서 1로 만드는 데 걸리는 최소 연산 횟수입니다.

D[i]= D[i-1]+1 그전의 횟수에 +1하는 기본 점화식을 하나 세웁니다.

D[i/3]+1 과 D[i/2]+1 과 D[i-1]+1 값을 비교하여 최소값을 구합니다.

 

1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	2	3	3	2	3

 

예1) D[2]의 값 구하기 (2에서 1로 만드는데 최소 연산 횟수)

D[2-1]+1 = 1

D[2/2] +1 = 1 최솟값을 구합니다

 

예2) D[3]의 값 구하기

D[3-1]+1 = 2

D[3/3] +1 = 1 최솟값을 구합니다

 

예3) D[4]의 값 구하기

D[4-1]+1 = 2

 

예4) D[5]의 값 구하기 

D[5-1]+1 = 3

 

예5) D[6]의 값 구하기 (6에서 1로 만드는데 최소 연산 횟수)

D[6-1]+1 = 4

D[6/3]+1 = 2 

D[6/2]+1 = 2 최솟값 구하기

 

=>5에서 1이 되는 연산에서 +1

6/3=2 2가 1이 되는 연산에서 +1

6/2=3 3이 1이 되는 연산에서 +1 에서 최솟값을 구하면 됩니다.

 

 

 

완성된 코드

import java.util.*;


public class Main {

	public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	
	
	int N = sc.nextInt(); //총 단지 수
	
	int[] D = new int[N+1];
	D[1]=0;
	
	for(int i=2; i<=N; i++) {
		D[i]= D[i-1]+1;
		if(i%2==0) D[i] = Math.min(D[i],D[i/2]+1);
		if(i%3==0) D[i] = Math.min(D[i],D[i/3]+1);
		
	}
	System.out.println(D[N]);
	}
	
	

	
}