[DP] 백준 1463 문제 풀이

 

 

처음에는 그냥 조건문을 만들어 그리디알고리즘 방식으로 계속 그때그때 작은수를 만들면서 짜면 될 줄 알았다. 

하지만 10을 입력으로 넣었을 때 예외가 발생하였고 우선순위를 정해놓고 짜는 방식으로는 하면 안되겠다는 생각이 들었다. 

위의 문제에서 의도한 풀이법은 DP 알고리즘을 이용하는 방식으로 점화식을 이용하는 것이 가장 좋다. 

DP(다이나믹 프로그래밍)란 큰 문제를 작은 문제로 나누어 푸는 방법이다. 이 작은 문제들은 어딘가에 저장해놓는다. 그리고 이 작은 문제들을 이용해서 답을 도출해낸다. 

f(n/2)+1

f(n/3)+1

f(n-1)+1

중 최솟값이 f(n)의 값이 된다. 

불필요한 연산을 여러번 하는 것을 막기 위해 리스트에 연산횟수를 저장해놓는다. 

 

예를 들어 10을 입력했을 경우 배열 인덱스 1부터 10까지 계산해 나간다. 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 

 x   0   1  1   2  3   2   3   3   2   3

 

이와 같이 저장이 된다. 

# DP 문제
# min(f(n/3)+1, f(n/2)+1, f(n-1)+1)

def main():
    n = int(input())

    count_list = [0 for _ in range(n + 1)]

    for i in range(1, n + 1):
        if i == 1:
            count_list[i] = 0
        else:
            count_list[i] = count_list[i - 1] + 1
            if i % 3 == 0 and count_list[i // 3] + 1 < count_list[i]:
                count_list[i] = count_list[i // 3] + 1
            if i % 2 == 0 and count_list[i // 2] + 1 < count_list[i]:
                count_list[i] = count_list[i // 2] + 1

    print(count_list[n])


if __name__ == '__main__':
    main()

 

코드는 이와 같다.