[이코테] 다이나믹 프로그래밍 - 1로 만들기

정답을 봐도 이걸 내가 생각해낼 수 있었을까 의문이 드는...

점화식 세워보는 걸 좀 연습해야 하나 싶기도 하고

 

1. 내 풀이

d = [0] * 30000

x = int(input())
def cal_cnt(x):
  if x == 1:
    return None
  elif x % 5 == 0:
    x //= 5
    d[x] = 1
    return cal_cnt(x)
  elif x % 3 == 0:
    x //= 3
    d[x] = 1
    return cal_cnt(x)
  elif x % 2 == 0:
    x //= 2
    d[x] = 1
    return cal_cnt(x)
  elif (x % 5 != 0) and (x % 3 != 0) and (x % 2 != 0):
    x -= 1
    d[x] = 1
    return cal_cnt(x)

cal_cnt(x) 
print(d)
print(d.count(1) + 1)

-> 이렇게 풀면 안 풀림

 

 

1-1. 풀이 도중 생각

1) 커다란 숫자를 일정한 연산을 반복하여 차근차근 줄여나가는 방식이니 다이나믹 프로그래밍, 그 중 탑다운 방식으로 풀어야 할 것 같다

2) 연산할 수 있는 도구들을 만들어놓고 그것들을 재귀함수 방식으로 풀어나가자

3) 연산횟수를 세야 하니 dp 테이블을 만들어보자 (원소가 3만개인 0 행렬을 만들어야 하는데 이게 맞나 싶기도 하고...)

 

2. 책 풀이

x = int(input())
d = [0] * 30001

# 다이나믹 프로그래밍 진행 (바텀업)
for i in range(2, x+1):
  # 현재의 수에서 1을 빼는 경우
  d[i] = d[i-1] + 1
  # 현재의 수가 2로 나눠떨어지는 경우
  if i % 2 == 0:
    d[i] = min(d[i], d[i//2]+1)
  # 현재의 수가 3로 나눠떨어지는 경우
  if i % 3 == 0:
    d[i] = min(d[i], d[i//3]+1)
  # 현재의 수가 2로 나눠떨어지는 경우
  if i % 5 == 0:
    d[i] = min(d[i], d[i//5]+1)

print(d[x])

풀이는 min을 활용하고, 바텀업 방식을 택했다...?

하나하나 대입하면서 풀면 풀어지는데 (신기).... 왜 저렇게 되는거지...?

 

3. 새롭게 알게 된 것 or 새삼 다시 알게 된 것

1) 그림을 그려서 다이나믹 프로그래밍 문항인지 확인해볼 수 있음

2) 점화식을 생각해내고, 그것을 코드로 구현해내기?