#1463 1로 만들기🤸‍♀️

문제📝

결과😍

코드💻

x = int(input())

d = [0]*(x+1)

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

print(d[x])

풀이💡

1. d에 계산된 값을 저장해둔다. x+1이라고 한 이유는 1번째 수는 d[1]이 아니고 d[2]이기 때문에 계산하기 편하게 d[1]을 1번째인 것처럼 만들어준다.
2. for문에서 1을 빼고 시작하는 이유 : 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문
3. if elif else문을 사용하면 안된다. if만 사용해야 세 연산을 다 거칠 수 있다.
4. min에서 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것이기 때문이다. d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.

-dp 문제이다.
동적 계획법은 메모이제이션 방법을 사용하여 중복해 계산되는 값을 저장해 효율을 높여준다.

dp문제 좀 어려운 것 같다...아직도 정확히 이해는 안되었지만 몇 번 반복하다보니 처음보다는 나은 것 같기두...계속 다시 풀어봐야겠다...

그리디로 풀 경우, 10은 10-5-4-2-1로 풀게 되므로 방법의 수가 5가 된다.

---

참고🙏

👉 [백준] 1463번: 1로 만들기 - 파이썬