백준 1463 : 1로 만들기

 

이 문제는 다이나믹 프로그래밍 문제이다. 먼저 이 글로 개념을 익히자.

위에 소개한 방법처럼 DP 테이블을 이용해서 풀면 된다! 이를 메모제이션 기법이라고도 한다.

오버헤드가 발생하는 탑다운 방식 보다 for문을 이용하는 바텀업 방식을 이용하겠다.

(바텀업 방식 : 가장 작은 데이터부터 쌓아 올리듯이 저장하는 개념)

X = int(input())

arr = [0] * (X+1)

for i in range(2, X+1):
  arr[i] = arr[i-1] + 1
  if i % 3 == 0:
    arr[i]= min(arr[i],arr[i//3]+1)
  if i % 2 == 0: 
	arr[i]= min(arr[i],arr[i//2]+1)

print(arr[X])

생각할 점 : 

1. 인덱스는 특정 값을 의미하고 저장된 값은 필요한 연산 횟수를 저장한다.

2. 1일 때는 연산 횟수가 0이다.

3. -1을 한 뒤 나눗셈 연산을 하는 경우와 나눗셈 연산을 먼저 하는 경우를 중 최솟값을 골라야한다.

4. -1을 먼저하는 점화식은 arr[i] = arr[i-1] + 1이고,

나눗셈을 먼저하는 경우의 점화식은 arr[i] = arr[i//3] + 1이다.