Algorithm, boj, 1로만들기(1463)

풀이

• 4 => 4/2=2, 2/2=1 또는 4-1=3, 3/3=1 두가지 방법이 있다
• 2로 나누어지면 ==> dp[i] = Math.min(dp[i-1]+1, dp[i/2]+1);
• 3으로 나누어지면 ==> dp[i] = Math.min(dp[i-1]+1, dp[i/3]+1);
• 2,3으로 나누어지지 않으면 dp[i] = dp[i-1]+1;

배운점

• 예제를 나열하고 규칙이 보이지 않으면 점화식을 생각해보자…!!!

package org.baekjoon;

import java.util.Scanner;

public class test1463 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();

		int[] dp = new int[num+1];
		dp[1] = 0;
		for (int i=2; i<num+1; i++) {
			dp[i] = dp[i-1]+1;
			// 해당 숫자가 2로 나눠떨어진다면, 2로나누거나, -1하는 방법 두가지가있다
			if (i % 2 == 0)
				dp[i] = Math.min(dp[i-1]+1, dp[i/2]+1);
			else if (i % 3 == 0)
				dp[i] = Math.min(dp[i-1]+1, dp[i/3]+1);

		}
		System.out.println(dp[num]);
	}
}

---

Reference

• 문제보러가기
• https://plplim.tistory.com/12

---