문제 링크
해당 문제를 처음 봤을 때, 어떠한 수가 주어졌을 때 3가지의 계산방식을 통해 1로 도달할 수 있는 최소 계산횟수를 구하는 문제라고 판단했다.
그래서, BFS 매커니즘을 통해 아래와 같이 해결하고자 하였다.
import sys
from collections import deque
def solution():
x = int(input())
function1 = lambda x: x//3
function2 = lambda x:x//2
function3 = lambda x:x-1
calList = deque([[x,0]])
while calList[0][0]!= 1:
nowValue,nowCnt = calList.popleft()
if nowValue%3==0:
calList.append([function1(nowValue),nowCnt+1])
if nowValue%2==0:
calList.append([function2(nowValue),nowCnt+1])
if nowValue>0:
calList.append([function3(nowValue),nowCnt+1])
print(calList[0][1])
solution()하지만, 시간초과가 발생하였다. 해당 문제를 위와 같은 알고리즘으로 풀 경우 최악의 상황에서 계산을 반복적으로 진행하여 시간초과가 발생할 것이라고 예측했다.
아래는 다이나믹 프로그래밍과 그리디 알고리즘의 개념이다.
다이나믹 프로그래밍 = 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임
그리디 알고리즘 = 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
위의 개념과 같이 그리디 알고리즘은 반례가 없을 경우 사용하고, 다이나믹 프로그래밍은 반례를 생각하고 최소값을 찾을 때 찾는 방법이라고 생각하면 편할 것 같다.
위의 문제는 10일 때 10 -> 5 -> 4 -> 2 -> 1이 아니라 10 -> 9 -> 3 -> 1임으로 단순히 3으로 나눌수 있으면 나눠 해결할 수 없는 반례가 존재한다. 이러한 근거를 통해서 다이나믹 프로그래밍을 사용하고자 하였다.
그리고, 다이나믹 프로그래밍의 메모이제이션방법을 사용하기 때문에, 앞의 문제였던 시간초과를 해결할수 있을 것이다.
def solution():
x = int(input())
calList = [0 for _ in range(x+1)]
for i in range(2,x+1):
calList[i] = calList[i-1]+1
if i % 3 == 0:
calList[i] = min(calList[i],calList[i//3]+1)
if i % 2 == 0:
calList[i] = min(calList[i],calList[i//2]+1)
print(calList[x])
solution()위의 코드와 같이 해결하였다. 시작(1)과 끝(x)가 주어졌기 때문에, 상향식으로 다이나믹 프로그래밍을 적용하였고, calList리스트의 인덱스는 타겟이 되는 수로 생각했고 해당 인덱스에 들어있는 값은 1부터 해당 인덱스까지 주어진 3가지 방법을 통해 도달할 수 있는 최소 계산 횟수를 담았다.
먼저, 1은 시작값이니 생략했고 인덱스를 2부터 시작하였다. 그리고 특정 인덱스는 전 인덱스에서 3번째 방법(-1하는 방법)을 적용하였고 만약 3이나 2로 나눠질 경우 해당 인덱스에 해당하는 리스트값과 전 3이나 2로 나눴을 때의 리스트값을 비교해서 최소값을 찾아 값을 변경하였다.
위와같은 방법을 통해서 첫번째 시도에서 하나하나 일일이 계산했던것에 비해, 한번 계산하면 계산된 값을 다시 사용할 수 있도록 진행(메모이제이션 방법)하여 시간 효율을 증가시켜 문제를 해결하였다.
