백준: 1463 1로 만들기

문제

1463번: 1로 만들기

 

문제 풀이

 문제는 특정 수가 1이 되기 위해서 2, 3으로 나누거나 -1을 하였을 때 최소 횟수로 1을 만드는 방법을 찾는 것이다. 효율적으로 문제를 풀기 위해 메모이제이션(memoization)을 통해 문제를 접근하면 시간초과를 발생시키지 않고 문제를 풀 수 있다.

 

Figure 1. 10일 경우의 메모이제이션

 문제를 푸는 방법은 그림 1과 같다. 그림 1은 10인 경우에 메모이제이션을 통해 값을 찾는 과정이다. 다음과 같은 과정을 반복하여 카운트 값을 누적시켜가는 방식을 사용한다.

• 각 인덱스는 실제 값을 의미한다. (1 ~ N)
• 입력된 값과 인덱스를 일치시키기 위해 0번 인덱스를 사용하지 않는다.
• 입력 값이 1인 경우, 횟수는 1이므로 별도의 메모이제이션이 필요 없다.
• 입력 값이 1보다 큰 경우 다음과 같은 과정을 통해 최소 카운트 횟수를 구할 수 있다.
  • 2로 나누어 떨어지는가?
  • 3으로 나누어 떨어지는가?
  • 위의 두 경우가 아니라면 바로 앞의 카운트 횟수에서 1을 추가한다

 그림 1의 예시를 보면, 2와 3은 각각 한번에 계산 할 수 있으므로 카운트 횟수는 1이다. 그다음 부터는 4의 경우 2로 나누어 떨어지고 몫은 2이기에 2의 카운트 횟수 + 1을 해주어 2라는 값을 기록한다. 이와 달리 5의 경우 2, 3으로 나누어 떨어지지 않으므로 바로 앞의 4의 합산된 카운트 수에 + 1을 하게 되면 5를 구하는 최소 횟수가 된다. 이런식으로 값을 기록해두고, 몫에 해당하는 값의 카운트 횟수를 확인하거나, 2와 3으로 나누어 떨어지지 않을 경우 바로 앞의 수에 대한 카운트를 확인하면 된다.

 

코드

if __name__ == "__main__":
    n = int(input())

    memo = [0] * (n + 1)

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

    print(memo[n])

 우선 바로 앞의 값에서 + 1을 한 후, 2와 3으로 나누어떨어지지 않는다면 해당 숫자의 카운트 횟수는 앞의 값 + 1이 된다. 즉 1을 빼야하는 상황은 그림 1에서 인덱스 5, 7, 10과 같은 경우이다.