알고리즘 분류 동적계획법
📎 문제 출처 1로 만들기
처음 문제를 보았을 때는 복잡할 것 같지는 않았다. 그리디로 해결하면 될 것 같다는 생각이 처음으로 들었지만 제시된 예제를 보고는 그리디는 아니라는 것을 알게 되었다.
만약 특정 방법이 문제 해결의 끝까지 반례 없이 적용이 된다면 그리디로 해결할 수 있는 문제가 맞다. 하지만 이 문제에서는 3으로 우선적으로 나누는 것이, 2로 나누는 것이 그렇다고 1로 차감하는 것이 문제 해결에 있어 최솟값을 찾는 것의 최적화된 방법이 아니다.
그래서 동적계획법으로 문제를 접근하였다.
🔗 코드
n=int(input())
d=[0]*(n+1)
for i in range(2,n+1):
d[i] = d[i-1]+1
if(i%2==0):
d[i]=min(d[i],d[i//2]+1)
if(i%3==0):
d[i]=min(d[i],d[i//3]+1)
print(d[n])
동적 계획법에도 상향식, 하향식 문제 풀이가 있다. 이 문제는 작은 수의 값으로부터 주어진 수까지 올라가는 상향식 방식으로 접근하였다.
우선 d[i]가 나타내는 것은 인덱스 i가 1까지 도달할 수 있는 최솟값이다.
따라서 for문이 인덱스 2부터 시작인 것은, d[1]은 어처피 0이라는 이유에서 위와 같이 설정한 것이다.
for문 안은 쉽게 말하면 1을 빼는 것, 2로 나누는 것, 3으로 나누는 것 중 최단 값을 구해 정하는 로직으로 구성되어 있다.
2,3으로 나누어지지 않는다면 1을 빼는 것이 필연적인 선택이다. 만약 2,3로 나누어진다면 현재 1을 뺀 값과 2로 나누어 생긴 값에 1을 더해 비교를 하여 나온 값의 min 값을 취한다.
핵심은 다음과 같다.
작은 값의 구해놓은 최솟 값들은 이미 최솟 값이라는 보장이 있기 때문에 그 값을 활용하여 더 큰 값을 구해나가는 것이다.
동구팔