[Java/백준/DP] 1463번: 1로 만들기

문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

코드

매번 새 유형 나오면 모르쇠,,,,, 슬프다.

 

우선 초기값, Working-backward는 

dp[0]과 dp[1]은 연산을 하지 않아도 되므로 0이다.

 

N==2 : N/2를 하거나 N-1를 하면 바로 1이 된다. → 연산 결과 1번

N==3 : N/3을 하면 바로 1이다 → 연산 결과 1번

N==4 : 3가지 경우의 수를 고려한다.

      ① N-1

          N-1을 하면 N=3 → N/3=1 (연산 결과 2번)

      ② N/2

          N/2를 하면 N=2 → N/2=1 (연산 결과 2번)

      ③ N/3

          N%3!=0 이므로 연산 불가능

①, ② 둘 다 연산 횟수는 2번 → 연산 결과 2번

 

N==4일 때의 경우에서 점화식을 유추해볼 수 있다.

① N-1

dp[N] = dp[N-1] + 1 (1은 N=N-1의 횟수)

② N/2

dp[N] = dp[N/2] + 1 (1은 N=N/2의 횟수)

③ N/3

dp[N] = dp[N/3] + 1 (1은 N=N/3의 횟수)

위 세가지 중 가장 작은 값을 택하면 된다.

 

배열 dp의 모든 원소의 값은 1에서부터 시작했으므로 위 과정이 모두 끝난 뒤 dp[N]의 값을 출력한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N+1];
		
		dp[0] = dp[1] = 0;
		
		for(int i=2; i<=N; i++) {
			dp[i] = dp[i-1] + 1;
			if(i%2==0) dp[i] = Math.min(dp[i/2]+1, dp[i]);
			if(i%3==0) dp[i] = Math.min(dp[i/3]+1, dp[i]);
		}
		
		bw.write(Integer.toString(dp[N])+"\n");
		bw.flush();
	}
}