[백준] 1463번: 1로 만들기 (다이나믹 프로그래밍)

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

1463번: 1로 만들기

 

이 문제는 다이나믹 프로그래밍으로 접근해서 풀어햐하는 문제이다.

(전의 결과를 다음 결과에 이용하게 되는, 점화식을 활용한 DP문제)

 

즉, 앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다.

 

만약 이 문제를 그리디로 접근해서 푼다면

큰 수로 처음부터 계속 나누는 것이 제일 빨리 1로 도달할 수 있는 방식일 것이다.

즉, 10 - 5 - 4 - 2 - 1 (총 4번의 연산).

 

그러나, 문제의 힌트 부분을 보면, 10 - 9 - 3 - 1 (총 3번의 연산), 다음의 방법이 최솟값이 된다.

 

따라서 DP를 이용해야 하고, 이는 왜냐하면 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우 모든 경우의 수 중 최솟값을 찾을 수 있기 때문이다.

 

n = int(input())
d = [0] * (n + 1)	## d에 계산된 값을 저장해둔다. n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문에, 계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.

for i in range(2, n + 1):
## 여기서 왜 if 1빼는 방법, 2 나누기, 3 나누기 동등하게 하지 않고 처음에 1을 빼고 시작하는지 의아해 할 수 있다.
## 1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다.
## 즉 셋 다 시도하는 방법이 맞다.

## 여기서 if elif else를 사용하면 안된다. if만 이용해야 세 연산을 다 거칠 수 있다, 가끔 if continue, else continue를 쓰는 분도 계신데, 난 이게 편한듯.
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)	## 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다. d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])

 

일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에

d[i] = d[i-1] + 1을 통해 횟수를 +1 추가 해준다.

그리고나서, d[i]가 2 와 3으로 나누어 떨어지는 경우에는

1을 빼는 것 보다 나누어 떨어지는게 훨씬 이득이기 때문에

min(d[i], d[i//2]+1)을 통해 최소값을 선택하면 된다.