728x90
▶1463 문제
▶ 문제풀이
- 동적 계획법 사용해야함 < fn(n) = fn(n-1) + fn(n-2) + ... + fn(0); >
점화식 : dp[n] = Math.min(dp[n-1], dp[n/2], dp[n/3]) + 1;
- 초기값 설정 : 위의 문제에서 1이 입력되었을 때 이미 1이기 때문에 0이 출력됨. (dp[1] = 0)
- dp[2] = dp[1] + 1 = 1;
- dp[3] = dp[1] + 1 = 1;
- dp[4] = dp[2] + 1 = 2;
- dp[5] = dp[4] + 1 = 3;
.....
- dp[10] = dp[9] + 1 = 3;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int[] dp = new int[num+1];
dp[0] = dp[1] = 0;
for(int i = 2; i <= num; i++) {
dp[i] = dp[i-1] + 1;
if(i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3]+1);
if(i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2]+1);
}
System.out.println(dp[num]);
br.close();
}
}
728x90
'Algorithm > BaekJoon[Java]' 카테고리의 다른 글
백준 11727 (0) | 2022.03.20 |
---|---|
백준 11726 (0) | 2022.03.19 |
백준 10991, 10992 (별찍기) (0) | 2022.03.18 |
백준 2438, 2439, 2440, 2441, 2442, 2445, 2446 (별찍기) (0) | 2022.03.17 |
백준 10818 (0) | 2022.03.17 |