[#1463] 1로 만들기

문제

#1463 1로 만들기
Silver3
적용 알고리즘: 동적 계획법 알고리즘

---

풀이 방법

• 초기 값, 처음 몇 개의 수와 목표하는 수를 알고 있으므로 상향식으로 접근한다.
• 메모이제이션 기법으로 기존에 계산한 값을 저장한다.
• 모든 경우를 다 탐색하고 가장 적은 값을 선택한다.
• 점화식을 세운다.
• 배열을 지정해서 해당 수 만드는데 필요한 연산의 수를 저장한다.
• 현재 구하려는 수를 본인 수-1 를 만드는데 걸린 값 + 1로 초기화 한다. 왜냐하면 현재 수에서 1을 빼면 이전의 수가 되기 때문이다.

코드 흐름

1. 사용자의 입력을 받고, 입력받은 수 만큼의 배열을 생성한다. (편의를 위해 n + 1)
2. 루프를 돌린다. 1의 값은 0으로 알고 있기 때문에, 2부터 돌린다. 이전 (이미 계산 횟수를 구해놓은 수의)수에서 1을 뺴면 현재 수가 되므로 현재 구하려는 값은 이전에 구해놓은 수 + 1로 초기화한다.
3. 만일 현재 수가 2로 나누어지면 현재 계산된 결과 값, 2로 나누었을 때의 계산 값 + 1 중에 더 작은 계산 횟수를 가진 값으로 저장한다.
4. 만일 현재 수가 3로 나누어지는 경우 현재 계산된 결과 값, 3로 나누었을 때의 계산 값 + 1 중에 더 작은 계산 횟수를 가진 값으로 저장한다.
5. n번째 인덱스를 계산할 때 까지 루프를 돌리고, 루프를 나와서 결과를 출력한다.

코드

# 1: 0번
# 2: 최소 1번
# 3: 최소 1번
# 4: 최소 2번 (2를 나눠 2 적용 or 1을 빼서 3 적용)
# 5: 최소 3번 (1뺀 후, 4 적용(최소 2))
# 6: 최소 3번 (2로 나눈 후 3 적용 or 1 뺀 후 5적용 or 3로 나눈 후 2적용)

n = int(input())
cnt = [0] * (n + 1)

for i in range(2, n + 1):
    cnt[i] = cnt[i - 1] + 1
    if (i % 2 == 0):
        cnt[i] = min(cnt[i], cnt[i // 2] + 1)
    if (i % 3 == 0):
        cnt[i] = min(cnt[i], cnt[i // 3] + 1)

print(cnt[n])

체감 난이도: 4.4/5
처음에는 이전에 풀었던 문제 BFS 알고리즘을 사용한 14226번 이모티콘 문제와 유사하다고 생각해서 그 문제를 참고하려고 했는데 적용방법을 모르겠다… 인터넷에 찾아보니까 BFS로도 풀 수 있는 것 같다.
낮은 수부터 점화식을 잘 세우는 것이 핵심이고 이게 가장 까다로운 것 같다. 그리고 처음에는 왜 1을 먼저 뺀 값에서 계산을 하는지 이해가 되지 않았는데, 일단 뺸값으로 초기화를 하고 나누었을 때의 값과 비교를 하여 min인 값을 선택하는 방법이다. 이 부분에서 약간의 이해와 아이디어가 필요했던 문제인 것 같다.