[실버 3] 1463번: 1로 만들기

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

1463번: 1로 만들기

---

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

사고의 흐름

• 그리디인가? 3으로 나누어 떨어지는지, 2로 나누어 떨어지는지 체크해서 나누어 떨어지면 무조건 나눠주는 게 1씩 빼는 것보다 이득이니까.
• 그런데 제출해보니 틀리네. 예제를 분석해보자.
• Input으로 10이 들어오면 내가 짠 알고리즘대로라면 2로 나누어 떨어지니까 10 → 5 → 4 → 2 → 1 총 4번 연산하는데, 실제로는 1을 뺀 다음 3으로 나눠서 10 → 9 → 3 → 1 3번 연산하는 게 답이네.
• 그러면 무조건 나누어 떨어진다고 나누기보다는 1을 빼면서 더 좋은 경우를 찾아야 하는구나. 그리디가 아니네.

 

• 문제는 어디까지 1씩 빼면서 더 좋은 경우를 찾아야 하는 거지? 주어진 Input보다 더 작은 모든 숫자를 탐색하면 되나?
• 그렇게 하면 너무 비효율적인데...더 좋은 방법이 없을까?
• 그러면 우선 처음 생각한 대로 나눌 수 있을 때 나누면서 연산 횟수를 카운팅한 다음, 연산 횟수보다 더 작은 횟수로 Input에서 1씩 빼면서 각각의 숫자에 대해 경우를 찾아보면 되지 않을까? 그런 식으로 하면 Input보다 더 작은 모든 숫자를 다 탐색할 필요가 없으니까.

 

• 작성한 로직은 맞는 것 같은데 왜 틀리지? 극단적인 케이스 고려를 안 해서 그런가? 예를 들면 Input으로 1이 들어왔을 때라던가.
• 그렇지는 않은데...뭐가 문제지? 잘 모르겠다.

내가 작성한 소스코드

# 틀렸습니다
from sys import stdin


def find_ans(num):
    cnt = 0

    while num > 1:
        if num % 3 == 0:
            num //= 3
        elif num % 2 == 0:
            num //= 2
        else:
            num -= 1

        cnt += 1

    return cnt


num = int(stdin.readline().rstrip())

cnt = find_ans(num)

ans = cnt
for i in range(1, cnt):
    ans = min(ans, (find_ans(num - i) + i))

print(ans)

남이 작성한 소스코드

wizardrabbit 님:
https://www.acmicpc.net/board/view/92152

피드백

• 나눗셈 연산 쓰면 변수의 Type이 int에서 float으로 바뀌니까 정수 나눗셈 연산(//)을 사용하자.
• 값이 빨리 줄어든다고 해서 최적해가 도출되지 않는다. 즉 3으로 나누기, 2로 나누기, 1을 빼기 사이에는 우선순위가 존재하지 않는다!
• DP를 배우고 다시 도전해보자.