백준 1463 1로 만들기
DP 문제 풀 때는 3가지 단계를 생각한다
1.
테이블 정의
2.
점화식 찾기
3.
초기값 정하기
1. 테이블 정의
DP[i] → 정수가 i를 1로 만들 때, 연산을 하는 횟수의 최소값
2. 점화식 찾기
D[12] = ?
3으로 나누거나
(D[12] = D[4] + 1) = (D[num] = D[num / 3] + 1)
2로 나누거나
(D[12] = D[6] + 1) = (D[num] = D[num / 2] + 1)
1을 빼거나
(D[12] = D[11] + 1) = (D[num] = D[num - 1] + 1)
→ D[12] = min (D[4] + 1, D[6] + 1, D[11] + 1)
→ D[num] = min (D[num / 3] + 1, D[num / 2] + 1, D[num - 1] + 1)
즉,
→ D[i] = min (3으로 나눌 때, 2로 나눌 때, 1을 뺄 때)
3. 초기값 정의하기
D[0] = D[1] = 0
JAVA
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arr = new int[num + 1];
arr[0] = arr[1] = 0;
for (int i = 2; i <= num; i++) {
arr[i] = arr[i - 1] + 1;
if (i % 2 == 0) {
arr[i] = Math.min(arr[i], arr[i / 2] + 1);
}
if (i % 3 == 0) {
arr[i] = Math.min(arr[i], arr[i / 3] + 1);
}
}
System.out.println(arr[num]);
}
}
Java
복사
Python
num = int(input())
arr = [0] * (num + 1)
for i in range(2, num+1):
arr[i] = arr[i - 1] + 1
if i % 2 == 0:
arr[i] = min(arr[i], arr[i // 2] + 1)
if i % 3 == 0:
arr[i] = min(arr[i], arr[i // 3] + 1)
print(arr[num])
Python
복사