[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)

---

문제

1463번: 1로 만들기

---

풀이

 

다이나믹 프로그래밍. 한국어로 동적 계획법을 이용해 풀어야 하는 문제이다.

 

동적 계획법은 상향식과 하향식이 있는데, 처음 두 수를 알기 때문에 상향식으로 문제를 풀었다.

상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고,

하향식은 맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다.

 

이 동적 계획법이 최솟값을 구하는 면에서 그리디 알고리즘이랑 뭐가 다른가 싶었는데,

그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례 없이 적용이 되는 경우에 이용하고,

동적 계획법은 가능성을 모두 두고 그 안에 최솟값을 찾을 수 있기 때문에 

뭔가 그리디와 브루트포스의 중간 같은 느낌이다.

 

한 예로, 위의 문제 기준으로 

그리디로 문제를 푼다면 당연히 큰 수로 처음부터 계속 나누는 것이 제일 빨리 1로 도달할 수 있을 것이다.

하지만, 10의 경우엔 10 - 5 - 4 - 2 - 1로 푸는 방법 보다,

처음부터 1을 빼고 10 - 9 - 3 - 1을 만드는 방법이 최솟값이다. 예상을 벗어난 것 이다!

그렇기에 동적 계획법을 이용한다.

동적 계획법으로 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우 모든 경우의 수 중 최솟값을 찾아낼 수 있기 때문이다.

 

또한 동적 계획법은 메모이제이션 방법을 사용해 중복해 계산되는 값을 저장해 효율을 높여준다.

 

한 예로, 피보나치 수열을 보자.

 

n번째 피보나치 수를 구하려면, n - 1번째 피보나치 수와 n - 2번째 피보나치 수의 합을 구해야 한다.

이를 알기 위해서는 제일 처음의 두 수를 알아야 점진적으로 목표한 수를 구할 수 있다.

하지만 4번째 수는, 3번째 수 + 2번째 수 이고, 

3번째 수는 결국 2번째 수와 1번째 수를 더한 합과 같기 때문에 중복된다.

 

5번째 수 = 1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5)

 

그렇기에, 제일 작은 수 부터 미리 계산된 값을 저장해두고 필요할 때 빼낼 수 있도록 한다.

 

사담이 길었고 위의 문제를 풀어보자.

 

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])

---

거의 처음 dp 경험이었고 머리가 안돌아가서 애썼기 때문에,

내가 헷갈리고 이해가 안 갔던 부분 중심으로 더 자세히 적었다.

 

도움이 되길 바라며...