[알고리즘] 백준 1463 : 1로 만들기 - S3

2023.05.15

import sys
input=sys.stdin.readline

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

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

print(d[x])

---

다른 풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

a = [0] * (N + 1)
a[1] = 0
for i in range(2, N + 1):
	a[i] = min(a[i // 2] + i % 2, a[i // 3] + i % 3) + 1
print(a[N])

---

check point

• DP테이블 초기화에서 런타임에러가 났었는데 ref로 해결.
  10**6은 1000000...

• 처음 풀이를 생각했을때 재귀 또는 그리디로 값에서 1까지 찾아가야한다고 생각했음

• 보텀업 방식(상향식)
  DP테이블 초기화에서 d[1]=0이 되어있기때문에, 아래와 같이 생각할 수 있음

  1. x까지 1을 더하는 경우
  2. 2를 곱하는 경우
  3. 3을 곱하는 경우
     각 경우의 결과로 최솟값이 d[i]에 저장

• 여기서 2 또는 3으로 나누어 떨어지는 경우의 구현 부분이 이해하기 어려웠는데
  1부터 x까지 값을 +1,x2,x3 을 최소한으로 반복한다고 생각한다면
  d[i] -> 1을 더하는 경우, d[i]=min(d[i], d[i//2]+1) -> 1을 더하는 경우보다 2를 곱하는게 더 작다면 d[i]=d[i//2]+1 인 셈.

• d[i//2]+1 에서
  d[i//2]는 d[i]에 (d[i//2]) x2를 한다면 x2에 해당하는 +1의 횟수를 저장하기 위함
  +1은 +1, x2, x3 의 계산 횟수를 구하는 것(d[i+1]에 저장)