[BOJ] #1463. 1로 만들기(Python)

mingguriguri·2022년 12월 10일
0
post-thumbnail

#1463. 1로 만들기

유형: 동적프로그래밍
작성일시: 2022년 11월 26일 오후 12:20

012345678910
00112323323

📖문제

정수 X에 대한 연산

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

→ 정수 N이 주어졌을 때, 위의 연산 세 개를 적절히 사용해 1을 만든다. 연산을 사용하는 횟수의 최솟값을 출력한다.

# 입력 1  
2      
# 출력 1
10
# 입력 2
1
# 출력 2
3

🔍분석

👀 문제 유형 파악하기

1. 나열

먼저 나열해본다.

ex) n = 10

012345678910
00112323323
  • 2 : 2/2 (1)
  • 3 : 3/3 (1)
  • 4 : 4/2, 2/2 (2)
  • 5: 5-1, 4/2, 2/2 (3) : -1하고 직전 수 더함
  • 6 : 6/3, 3/3 (2) or 6/2, 3/3 (2)
  • 7 : 7-1, 6/3, 3/3 (3) : -1하고 직전 수 더함
  • 8 : 8/2, 4/2, 2/2 (3)
  • 9 : 9/3, 3/3 (2)
  • 10 : 10-1, 9/3, 3/3(3) or 10/2, 5-1, 4/2, 2/2 (4)
  • 11 : 11-1, 10-1, 9/3, 3/3 (4) : -1하고 직전 수 더함
  • 12 : 12/3, 4/2, 2/2 (3) , 12/2, 6/2, 3/3(3), 12/2, 6/3, 2/2 (3)
  • 13 : 13-1, 12/3, 4/2, 2/2 (4) : -1하고 직전 거 더함
  • 14: 14/2, 7-1, 6/3, 2/2 () ⇒ 횟수 4
  • 15 : 15-1, 14/2, 7-1, 6/3, 2/2 (5) or 15/3, 5-1, 4/2, 2/2 (4)
  • 16 : 16/2, 8/2, 4/2, 2/2 (4)
  • 17 : 17-1, 16/2, 8/2, 4/2, 2/2 (5) : -1하고 직전 수 더함

2. 규칙성 발견

열거함으로써 규칙성을 발견했다.

  • 2의 배수 → 2로 나누어 떨어질 때까지의 연산횟수
  • 3의 배수 → 3으로 나누어 떨어질 때까지의 연산횟수
  • 2와 3의 공배수 → 2나 3으로 나누어 떨어질 때까지의 연산횟수
  • 2와 3으로 나누어 떨어지지 않는 수 → -1 + 직전 횟수
    - 이렇게 하면 나누어 떨어지는 수로 만들어진다. 바로 그 직전 수가 되기 때문에 그 직전 수의 연산횟수를 더한다.
    - 번외 ) 2와 3 모두 나누기가 가능할 때, 3으로 먼저 나누는 것이 연산횟수가 더 적어진다. if문 사용할 때 3으로 나누는 연산을 먼저 한다.

하지만 예외 존재!

📢 ex) 10, 15

위에서 나열했을 때, 10의 값은 2로 나눈 값이 아니라 먼저 -1을 빼야 최소횟수가 나온다.

10 : 10-1, 9/3, 3/3(3) or 10/2, 5-1, 4/2, 2/2 (4)

하지만 15의 경우는 먼저 1을 뺀 것이 아니라 3으로 나누고 나서 연산하는 것이 최소횟수가 나온다.

15 : 15-1, 14/2, 7-1, 6/3, 2/2 (5) or 15/3, 5-1, 4/2, 2/2 (4)

⇒ 따라서, 무조건적으로 -1을 먼저 연산하거나, 나누기 연산을 먼저 하는 것이 아니라, 두 연산 모두 거친 후 둘 중의 최솟값을 비교하는 방식으로 가야 한다. (min함수 사용)


👀 리스트값과 인덱스 변수의 의미 파악하기

→ 각각의 테이블에는 해당 인덱스의 숫자가 1이 된다. 이 1이 되는데 필요한 연산의 수가 저장된다.

  • 테이블에 들어가야 할 것 : 최소 턴 개수 (출력하기 위함)
  • 테이블 인덱스가 의미하는 것 : 1~n
index (1~n)123n
최소 턴 개수

💡풀이

Bottom Up 방식

n = int(input()) # 수 입력 받기
dp = [0] * (n+1) #dp 리스트 초기화 

for i in range(2, n+1): #2부터 n까지 반복
    dp[i] = dp[i-1] + 1 #1을 빼는 연산 (1회 진행)
    if i % 3 == 0: # 3으로 나누어 떨어질 때, 3으로 나누는 연산
        dp[i] = min(dp[i], dp[i//3]+1)
    if i % 2 == 0: #2로 나누어 떨어질 때, 2로 나누는 연산
        dp[i] = min(dp[i], dp[i//2]+1)

print(dp[n]) #출력
  • 변수 n에 입력 받는다
  • dp리스트에 0이 n+1개 있는 리스트로 초기화한다
    • dp는 인덱스의 숫자가 1이 되는데 필요한 연산의 최솟값이 들어간다.
      • 즉, dp[1] = 0이다. 1이 1로 되는데 필요한 연산횟수는 0이기 때문이다.
      • dp[2] = 1이다. 2가 1로 되기 위한 연산은 2/2인 1이 된다.
  • for i in range (2, n+1) : 2부터 n까지 i로 반복한다.
    • 이때 2부터 시작하는 이유는 0과 1은 연산하지 않아도 0이기 때문이다.
  • dp[i] = dp[i-1] + 1 : dp[1] 는 숫자가 i가 1이 되는데 걸리는 최소한의 연산횟수를 저장해야 한다.
    • i에서 1을 빼면 i-1이 된다.
    • dp[i-1] 에 +1을 하여, dp[i-1] (i=1이 1이 되는데 필요한 최소한의 연산) + 1(i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화한다.
  • **if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1)** :: i가 3으로 나누어 떨어질 때, dp[i]dp[i//3] + 1 중 최솟값을 dp[i]에 저장한다.
    • dp[i]는 위에서 초기화한 dp[i-1]의 값이 들어가 있다. dp[i//3]+1은 i를 3으로 나눈 값이 1이 되는데 걸린 최소 연산횟수 + i를 3으로 나눈 연산횟수 1회이다.
  • if i%2==0: d[i]=min(d[i],d[i//2]+1)
    i가 2로 나누어 떨어질 때, dp[i]와 dp[i//2]+1 중 최솟값을 dp[i]에 저장한다. 위의 연산과 과정이 동일하다.
  • 이렇게 for문을 반복하면 dp[n]에는 n이 1이 되는데 필요한 연산의 최소 횟수가 들어간다. 따라서 dp[n]을 출력하면 된다

다른 풀이 참고

[백준] 1463 1로 만들기 (DP) - Python / 자세한 설명 / 여러가지 풀이 / 실버1

🤔회고

  • DP 문제를 드디어 혼자 힘으로 80%정도 풀었다. 이전까지는 헷갈렸는데, 이전보다는 문제 푸는 힘이 늘었다.
  • 경우의 수가 많은 문제는 일단 나열해본다! 나열하고나서 규칙성이 보이거나 어떠한 수들이 반복이 된다면 DP를 고려해보자!
profile
To be "irreplaceable"

0개의 댓글