1463. 1로 만들기

문제

백준 1463번 1로 만들기

---

풀이

기초적인 다이나믹 프로그래밍 문제였다. (근데도 푸는데 오래걸렸다.)

- 1, / 2, / 3 이 세가지를 이용하여 1을 만들 때 최소 연산 횟수를 구하는 문제다.

n을 1로 만들 때 오로지 - 1만 사용하는 경우에 가장 연산을 많이한다.
총 n-1번의 연산이 필요하다.
마찬가지로 n을 i로 만들 때 - 1만 사용한다면 총 n-i번의 연산을 해야한다.

그래서 리스트 dy[0]~dy[n]를 n~0으로 초기화하고 시작한다.

다음은 다시 리스트를 역으로 탐색하면서 - 1, / 2, / 3을 이용해 숫자 i를 만들 때 가장 적은 연산횟수를 저장해준다.

n = int(input())
dy = [n-i for i in range(n+1)]

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

---

부족한 점

기본 문제들부터 계속 연습해서 풀이 속도 높여야함