[ 백준 1463] ( python ) 1로 만들기

 

 

📚 1로 만들기

 

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

 

 

 

 

✍ 접근

• DP에 익숙하지 않아서 DFS로 풀려다가 계속 시간초과가 났었다.
• DP에 대한 기본적인 개념이 없어서 DP에 대해 공부 후 다른 사람의 코드를 참고해서 다시 풀어보았다.

 

 

 

정답 코드

N = int(input())
dy = [0]*(N+1)

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

이 짧은 코드를 위해 얼마나 고민했던가..

기본적인 DP 알고리즘 내용은 다른 포스팅으로 말하기로 하자

 

• dy라는 리스트에 0으로 초기화된 배열을 만들어준다. 길이는 정수 N에서 1을 더한 값(리스트 크기 고려)
•  for문을 돌며 하나하나 가능한 방법들을 따져본다
  = 문제에서 말한 가능한 연산 을 하나하나 해 보는 것
  
  이해가 잘 가지 않는다면(나) 간단하게 생각해보면 된다.
  ❓ 만약 N이 1이라면 ❗ 최솟값은 1이 된다
  ❓ 만약 N이 2이라면 ❗ 최솟값은 1이 된다 min( 1을 두번 뺀 값 = 2, 2를 한번 나눈 값 = 1)
  규칙이 살살 보이기 시작한다
  DP의 핵심은 규칙 찾기이다! + memoization
  
  ❔ 만약 N이 i라면 ❕ min( i-1에서 1을 더하거나 , i가 2로 나뉜다면 i//2의 몫에서 1을 더하거나, i가 3으로 나뉜다면 i//3의 몫에서 1을 더하거나)
   
  조금 더 자세하게 설명해보자! 
  만약 i가 6이라면 6까지 갈 수 있는 방법은 3가지가 있다.
  5 + 1 => 6
  2 * 3 => 6
  3 * 2 => 6
  
  따라서 우리가 만들어둔 memoization 리스트인 dy에서 dy[5],dy[2],dy[3]을 찾아서 1씩 더해준 값을 비교해서 가장 작은 값을 dy[i]에 넣어주면 된다
  
  정답 코드는 이 얘기를 코드로 하는 것!
  
  

 

⭐ 배움

• DP의 점화식에 대해 배웠다
• 커다란 덩어리로 생각하기보다는 작은 단위로 쪼개서 생각하면 DP는 쉽게 풀 수 있다.