[모각코] 210724 Today I Learned

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

 

 

 

x = int(input())
dp = [0 for i in range(x+1)]

for i in range(2, x+1):
    if i ==2 or i ==3:    # 초기화
        dp[i] = 1
    else:
        dp[i] = dp[i-1] + 1
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[int(i/3)] + 1)
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[int(i/2)] + 1)          

print(dp[-1])

 

 

정수 N이 주어졌을 때, 연산 세 개를 사용해서 1을 만드는 문제인데, 나는 반대로 1을 N으로 만드는 방법을 생각했다. 리스트 각각의 인덱스가 숫자를 의미해 그 인덱스까지 도달하는 데 필요한 최소 연산 수를 저장해나가는 알고리즘이다. 즉, 리스트 dp에 각각의 인덱스까지 도달하는 데 필요한 최소 연산 수가 저장되는 것이다. dp[2]에는 숫자 2가 되는 데 필요한 최소 연산 수 (1), dp[3]에는 숫자 3이 되는 데 필요한 최소 연산 수 (1) ... 이렇게 값이 저장된다. 작은 수부터 차례대로 최소 연산 수를 구해나가 마지막 dp[x]에 도달했을 때 그 값이 x가 1이 되는 데 필요한 최소 연산 수가 된다.

 

기본적으로 dp[i]는 dp[i-1]에 1을 더한 경우로 생각하고, 만약 3으로 나누어질 경우 3으로 나누었을 때 연산 수와 기존 값을 비교해 더 작은 수를 저장하고, 마찬가지로 2로 나누어질 경우 기존 값과 비교해 더 작은 수를 저장한다.