[백준, DP] 1463_1로 만들기

DP 알고리즘의 기초? 좋은 예제가 되는 문제인 것 같다. 유사한 형태의 DP 문제들이 있고 보고 있는 '이것이 코딩 테스트다' 에서도 유사한 문제가 있다.

 

DP 알고리즘에 대해 공부를 하긴 했지만 점화식을 찾는 것과 재귀를 통해 구현하는 부분이 약한 것 같아 직접 제대로 풀어봤다. 2-3시간 투자한 것 같은데.. 흠... 노력하자.

 

1. 바텀업 방식

- 구현하는데 매우 쉬웠다.

 

점화식이 d[i] = min(d[i-1], d[i // 2], d[i // 3]) + 1 로 들어온 값들을 3으로 나눌지, 2로 나눌지 아니면 1을 뺄지 구분만 잘 해준 뒤 DP 테이블에 작성해두면 된다.

 

주의했어야 하는 부분이 있었다.

- 조건으로 % 3, % 2 를 통해 실수값이 나올 수 없다고 생각해 dp[i / 3], dp[i / 2] 로 해서 문제가 없을 것으로 판단했지만 float 형태로 인식해 에러 발생

- // 를 사용해 확실하게 int 형으로 수정해야했다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
val = int(input())

dp = [-1] * (val+1)
dp[1] = 0

# 바텀업
for i in range(2, val+1):
    dp[i] = dp[i-1] + 1 # 우선 -1을 한 걸로 초기화
    
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
        # 그냥 / 를 쓰면 float 자료형으로 인식해서 // 로 확실하게 int로 만들어주기
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[val])

 

 

2. 탑다운

문제 처음 봤을 때, 탑다운 방식으로 푸는 방법을 생각했다. 아이디어 방향과 접근 방식은 생각하기 쉬웠는데 구현이 어려웠다.

 

- 머리 아팠다

 

아직도 의문이 드는 부분이 있다.

3과 2의 공배수, 즉 6의 배수인 경우, 1. 3으로 나눈 경우, 2. 2로 나눈 경우, 3. 1을 뺀 경우, 총 3가지의 경우를 재귀 함수를 돌려 비교해야한다고 생각했다.

그러나 시간초과가 발생했다.

1을 뺀 경우는 고려하지 않고 돌리니 정답이었다. 사실 반례가 존재할 수도 있어서 추가해야하는 게 맞는 것 같은데 반례가 없어서 정답이 된 듯 하다. 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
val = int(input())

def top(value):
    if dp[value] != -1:
        return dp[value]
    
    if value % 3 == 0 and value % 2 == 0:
        dp[value] = 1 + min(top(value // 3), top(value // 2))
        # 3으로 나눴을때, 2로 나눴을때, 1을 뺐을때, 3가지 경우를 비교해야한다고 판단
        # min(top(value // 3), top(value // 2), top(value-1))을 넣으니 시간 초과 발생
        
    elif value % 3 == 0:
        dp[value] = 1 + min(top(value - 1), top(value//3))
    elif value % 2 == 0:
        dp[value] = 1 + min(top(value - 1), top(value // 2))
    else:
        dp[value] = 1 + top(value-1)
            # 마지막에 value 대신 dp[value-1]을 넣어서 동작 안했음
            # 1시간 동안 찾았다
			
    return dp[value]

dp = [-1] * (val+1)
dp[1] = 0
print(top(val))

# 재귀함수는 항상 머리 아프다
# 헷갈리지만 계속 해보면서 익숙해져야함