[Algorithm] 백준_1463번: 1로 만들기

오늘의 문제는 🚀 백준 1463 - 1로 만들기이다.

DP 알고리즘의 시작! 인강이랑 같이 가보자고~

테스트케이스 이해하기

위의 세가지 방법을 가장 적게 사용해서 1를 만들수 있는 최솟값을 찾는 것이다!

정답코드

해당 문제는 다이나믹 프로그래밍으로 해결해야 해서, 처음은 top-down 방식으로 문제를 해결했다.

• memo = 최소 연산의 횟수 저장소

• memo[n] = (memo[n-1] +1) or (memo[n//2] +1) or (memo[n//3]+1)

1. 인풋과 memo할 수 있는 배열을 선언한다.

2. 재귀함수를 선언한다.

   1. 1이면 0을 리턴한다
   2. 이미 memo에 채워진 값이 있다면 리턴한다
   3. 가능한 세가지 경우(나누기 3, 나누기2, 1빼기) 중에 가장 적은 숫자를 저장한다.

3. 재귀를 프린트 한다.

하지만, 파이썬은 재귀의 깊이가 정해 져있기 때문에 어느 정도를 넘어가면 스택 오버플로우가 발생한다.

예전에 알고있었는데 잊고 있었다가 깜짝놀랬다….ㅋㅋㅋㅠㅠ

#벗뜨 파이썬은 재귀로 문제를 풀면 안된다....
n = int(input())
memo = [0]*(n+1)

def go(n):
    if n == 1:
        return 0
    elif memo[n] > 0:
        return memo[n]
    else:
        memo[n] = go(n-1) + 1
        if n%2 == 0:
            temp = go(n//2)+1
            if memo[n] > temp:
                memo[n] = temp
        if n%3 == 0:
            temp = go(n//3)+1
            if memo[n] > temp:
                memo[n] = temp
        return memo[n]

print(go(n))

그래서 재귀를 쓰지 않기 위해 bottom-up 반복문으로 바꾸어보았다. 그래서 통과!

n=int(input())
memo =[0]*(n+1)
for i in range(2, n+1):
    memo[i] = memo[i-1] + 1
    if i % 2 == 0:
        temp = memo[i // 2] + 1
        if memo[i] > temp:
            memo[i] = temp

    if i % 3 == 0:
        temp = memo[i // 3] + 1
        if memo[i] > temp:
            memo[i] = temp

print(memo[n])

🚀Reference: 백준 1463 - 1로 만들기