[백준] 1463 - 1로 만들기 (Java)

[백준] 1463 - 1로 만들기 (Java)

문제

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

풀이/후기

이코테에서 풀었던 1로 만들기와 거의 똑같은 문제였다.

차이점은 5 연산식이 없다는 것.

문제 복습을 위해 점화식을 직접 만들어봤는데,

몇 시간 전에 비슷한 문제를 풀었는데도 한 번에 잘 떠오르지 않았다.

복습이 중요할 것 같다...^^

https://da-zzling.tistory.com/35

점화식을 찾아내기 위한 몸부림

코드

package DynamicProgramming;

import java.io.*;

public class Problem1463 {
	
	static int[] d = new int[1000000+1];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		d[1] = 0;
		d[2] = 1;
		d[3] = 1;
		for (int i=2; i<N+1; 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]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/26813d82d868b9fec61c70003e641d718a53a307

참고