백준 1463 - 1로 만들기 (파이썬, DP)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

1로 만들기는 다이나믹 프로그래밍에서 아주 유명한 문제다.

옛날에 알고리즘 진짜 ㅇ도 모르던 시절에 도전했었는데 막 풀다가 실패했다가

다이나믹 프로그래밍을 공부하면서 다시 마주치게 되었다.

근데 어렵다...ㅎㅎ

 

n = int(input())

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


def makeone(n):
    for i in range(2, n+1):
        memo[i] = memo[i-1] + 1
        if i % 2 == 0 and memo[i] > memo[i//2] + 1:
            memo[i] = memo[i//2] + 1
        if i % 3 == 0 and memo[i] > memo[i//3] + 1:
            memo[i] = memo[i//3] + 1
    return memo[n]


print(makeone(n))

일단 이건 나의 허접한 소스이다ㅋㅋㅋㅎㅎㅎ

makeone이라는 함수를 만들었고,

n을 입력받은 뒤, memo[2] 부터 Bottom-Up 방식으로 memo라는 리스트에 쌓아나가는 방식이다.

(memo[0]은 없다고 치고, memo[1] = 0 이므로 memo[2]부터 쌓아나간다.)

 

먼저, memo[i] 는 세 가지로 표현될 수 있다.

memo[i] = memo[i-1] + 1

memo[i] = memo[i//2] + 1

memo[i] = memo[i//3] + 1

 

(여기서 i/2, i/3으로 적게되면 float 자료형이 나와서 에러가 뜬다.)

 

저 세가지를 차례로 거쳐가면서 가장 작은 것을 memo[i] 에 저장하는 방식이다.

그냥 피피티 보면서 그대로 풀었다...

 

 

근데 백준에서 1등 풀이를 봤는데,,,, 너무 깔끔해서 감동했다....

s={1:0,2:1}
def f(n):
 if n in s:
  return s[n]
 m=1+min(f(n//2)+n%2,f(n//3)+n%3)
 s[n]=m
 return m
print(f(int(input())))

일단, 리스트는 사용안하고 딕셔너리를 사용했다. (여기서부터 메모리차이가 엄청 났을것이다.)

그리고 Top-Down 방식이다.

n을 입력받았을 때, n이 딕셔너리에 등록되어 있다면 그대로 return 해주고,

만약 그렇지 않다면

 m=1+min(f(n//2)+n%2,f(n//3)+n%3)

이 식이 진짜 천재였던게,

2로도, 3으로도 나누어떨어지지 않을 때

나는 memo[i] = memo[i-1] + 1 이렇게 그대로 썼는데

이 분은 저 n%2, n%3을 더해줌으로써 이걸 해결했다.

그래서 min도 두개 중에 하나를 고르면 되는 식이 탄생한 것이다....!!!

 

다이나믹 프로그래밍 거의 첫 문제풀이였는데 앞으로 더 많이 풀면서 Bottom-Up과 Top-Down 방식 많이 익숙해져야겠다..!