[Python][백준/BOJ] 1463번 : 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

내 코드

import sys
input = sys.stdin.readline

n  = int(input())
dp = [0]*(n+1) #계산한 결과값을 더해주는 것이 아니라, 몇 번 계산했는지를 더해줄 것임
for i in range(2, n+1):
    dp[i] = dp[i-1]+1 #한 번 더 계산했다는 뜻
    if i%3==0: 
        dp[i]= min(dp[i], dp[i//3]+1)#만약 i가 9라면 이미 i//3인 3에는 그 때의 계산 결과값이 있을 것임. 그걸 불러오는 것이다.
    if i%2 ==0:
        dp[i] = min(dp[i], dp[i//2]+1) #지금의 계산 횟수가 작느냐, i//2를 했을 때에서 +1(지금것까지) 했을 때가 작은지의 차이
print(dp[n])

 

코드 리뷰

해당 문제에서 그리디 알고리즘을 쓰지 않은 이유는, 단순히 3을 나누거나 2를 나누는 등의 일정한 규칙에 의해서 최적의 해를 구할 수 있는 상황이 아니었기 때문이다. 모든 경우의 수를 따져보아야 하기 때문에 DP를 사용했다.

동적계획법(DP)은 상향식과 하향식이 있다. 이번 문제는 처음 수를 알고있고, 최종 목표하는 1을 만들어내는 것이므로 상향식으로 풀었다. 

그리고 너무 당연하게도 1을 빼는 연산을 통해 값을 구하는 것보다, 3으로 나누면서 수를 줄여나가는 것이 가장 빠르다.

점화식

점화식을 구해보면 위와 같다.

for i in range(2, n+1):

여기 보면 2부터 n까지 i를 돌린다는 것을 볼 수 있다. 이렇게 돌리는 이유는 dp[0]과 dp[1]은 필요없기 때문이다. 

생각해보면 dp[0]은 우선 나누고 빼서 1을 만들어야 하므로 1보다 작은 수로는 불가능하니까 필요가 없다.

그리고 dp[1]은 0으로 초기화하면, 그 자체가 곧 답이므로 for문에 넣을 필요가 없다.

 

DP

상향식(Bottom-up)

• 아래 → 위
• 아래쪽에서부터 작은 문제들을 해결하면서, 최종 목표하는 값을 구하는 것이다. 
• 반복문을 사용해서 구하는 것이 일반적이다.
• 부분해의 결과를 임시적으로 저장하는 DP 테이블을 사용한다.

 

하향식(Top-down)

• 큰 문제를 작은 문제로 나누어 작은 문제들의 해를 재귀적으로 구한다.
• 한 번 계산된 결과를 기억하기 위해 메모이제이션 기법을 이용한다.

메모이제이션

• 문제를 다시 호출하면, 메모리에 저장했던 결과를 가져온다.
• 이 특성으로 인해 일반적인 재귀 호출에 비해 실행 시간을 줄일 수 있다.

if (d[x] != 0) 
        return d[x]
else:
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

예를 들자면 위와 같다. 이미 d라는 배열 안에 결과값이 있다면 다시 계산하지 않는다.

그래서 피보나치 수열을 예로 많이 드는데, 피보나치 수열의 단순 재귀함수 시간복잡도는 O(2^n)이다.

하지만 동적계획법으로 피보나치 수열을 풀어낸다면 O(N)이다.

 

그리디 알고리즘과 차이

그리디 알고리즘 : 최적의 방법이 반례 없이 끝까지 적용

동적 계획법 : 모든 가능성을 두고, 그 안에서 목표 값을 찾음