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

DP문제 푸는 내내 점화식을 한번도 못찾았네요

이번 문제 또한 다른 분들의 코드를 참고했습니다.

경로를 찾는데 그 시점을 달리하여 문제를 키를 찾는 것은

너무 어려운 것 같습니다.

풀이를 시작할 때도 N부터 차근차근 내려올 생각밖에 못했지

1부터 올라와 최소값을 비교해서 찾는다는 방식은

꿈에도 몰랐습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); 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]>dp[i/2]+1) dp[i]=dp[i/2]+1; if( (i%3==0) && dp[i]>dp[i/3]+1) dp[i]=dp[i/3]+1; } System.out.println(dp[N]); } }