[python] 백준 1463 - 1로 만들기

출처 : 백준, https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

첫 번째 풀이 : 실패

 

if __name__ == '__main__':
  n = int(input())
  count = 0

  while n != 1:
    if n % 2 == 1: #홀수
      if n % 3 == 0:
        n //= 3
      else:
        n -= 1
    else:#짝수
      if n % 3 == 0:
        n //= 3
      else:
        if (n-1) % 3 == 0:
          n -= 1
        else:
          n //= 2

    count += 1

  print(count)

125
10

#8

 

 

두 번째 풀이 : 실패

 

if __name__ == '__main__':
  n = int(input())
  count = 0

  while n != 1:
    if n % 2 == 1: #홀수
      if n % 3 == 0:
        n //= 3
      else:
        n -= 1
    else:#짝수
      if n % 3 == 0:
        n //= 3
      elif n % 3 == 1: #3n + 1인 짝수라면
        if (n // 2) % 2 == 1 and (n // 2) % 3 != 0:
          n -= 1
        else:
          n //= 2
      else:
        n //= 2

    count += 1

  print(count)

1000
10

#9

 

첫 번째 풀이와 두 번째 풀이는

n이 3의 배수이면 3으로, 짝수라면 2로, 둘 다 아니라면 -1을 1이 될 때까지 하는 방식의 변형들이다.

물론 둘 다 실패했다.

 

 

세 번째 풀이 : DP

 

if __name__ == '__main__':
  n = int(input())
  step = [0] * (n+1)

  INF = 10e6 + 5
  
  for i in range(2, n+1):
    A = step[i // 3] if i % 3 == 0 else INF
    B = step[i // 2] if i % 2 == 0 else INF
    C = step[i - 1]

    step[i] = min(A, B, C) + 1

  print(step[n])

 

대체 뭐가 문제인가 싶어서 알고리즘 분류를 봤는데 다이나믹 프로그래밍인 것을 보고 머리가 띵했다.

그리고 DP라고 생각하니 정말 금방 문제가 풀리더라.

 

일단 DP이므로 점화식을 세워보자.

X가 1이 될 때 까지의 최소 횟수 step[X]라하면,

 

step[X] = min(step[X//3], step[X//2], step[X-1]) + 1(X≥2), step[1] = 0 (단, 나누어 떨어지지 않을 경우 무한)

 

라 세울 수 있다.

1에서부터 X까지 올라간다고 생각해보면 1에서 X까지 도달하기 위한 최소 횟수는

X//3까지의 최소 횟수와 X//2까지의 최소 횟수와 X-1까지의 최소 횟수 중 최소값에 +1을 한 것이기 때문이다.

---

 

시간 복잡도

 

O(n)

 

 

고찰

 

왜 DP인지 모르겠는데? 왜 DP인가?

 

항상 막히는 부분이 이런건데 어떤 알고리즘을 써야하는지 몰라서 잘못된 풀이를 작성해 문제를 풀지 못하는 경우가 많다.

이를 위해서 이 문제에서 DP를 써야하는 것을 어떻게 추론할 수 있는지 적어놓고자 한다.

 

먼저 이 문제는 1까지 도달하는데 걸리는 과정의 최소 횟수를 구하는 문제이다.

여기서 '최소 횟수'라는 말이 중요한데 즉, 이는 최솟값을 구하는 최적화 문제에 해당한다.

 

대학 알고리즘 과정 중 배우는 알고리즘은 다음과 같다.

 

1. Complexity
2. Recursion
3. Divide and Conquer + Sorting
4, 완전 탐색
5. Greedy
6. Backtracking
7. DP
8. Graph : BFS, DFS, Minimun Spanning Tree, Shortest Path
9. NP

 

이 중 최적화 문제에 쓰이는 대표적인 알고리즘은 바로

 

5. Greedy
7. DP

 

이다. 그렇다면 이 문제는 최적화 문제이므로 이 2가지 알고리즘으로 먼저 접근해보아야 하는데,

Greedy는 치명적인 단점을 가지고 있는 것이 바로 현재에 선택한 최선이 결과적으로 최선이어야 한다는 점이다.

이를 바탕으로 위 문제에서 현재에 최선인 값을 뽑아보면, X값을 가장 많이 줄일수록 최선이므로

 

X가 3의 배수일 때, 3으로 나누기

X가 2의 배수일 때, 2로 나누기

X가 둘 다 아닐 때, 1만큼 빼기

 

이다. 그리고 이는 예제 중 10이 10 -> 9 -> 3 -> 1로 진행되는 점만 보아도 아니라는 것을 알 수 있다.

10에서의 최선은 2의 배수이므로 2로 나누어 5가 되는 것인데, 실제 최소 횟수는 -1을 빼 9로 가는 방법이기 때문이다.

이를 통해 이 문제는 Greedy로 푸는 문제가 아니라고 결론 낼 수 있다.

(내가 실패한 첫 번째, 두 번째 풀이가 Greedy 방식으로 풀려 시도한 것이었다.)

 

그렇다면 DP인지 체크하기 위해 점화식을 세워봐야하는데, 점화식은 아래와 같이 바로 세워지는 것을 확인할 수 있다.

 

step[X] = min(step[X//3], step[X//2], step[X-1]) + 1(X≥2), step[1] = 0 (단, 나누어 떨어지지 않을 경우 무한)

 

여기서 이 문제는 DP로 풀어야한다는 것을 확정지을 수 있는 것이다.

 

즉, 오늘과 같은 실수를 하지 않기 위해서는 

 

1. 무엇이 목표인지 먼저 파악하고 최적화 문제로 파악된다면, Greedy와 DP를 먼저 시도해본다.

2. Greedy가 쉬우므로 먼저 체크해보고, 아니거나 애매하다면 DP인지 확인하기 위해 점화식을 체크해본다.