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

mingguriguri·2022년 12월 10일

DP python 백준 알고리즘

Python으로 공부하는 Algorithm

목록 보기

8/10

#1463. 1로 만들기

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

0	1	2	3	4	5	6	7	8	9	10
0	0	1	1	2	3	2	3	3	2	3

📖문제

정수 X에 대한 연산

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

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

# 입력 1  
2      
# 출력 1
10

# 입력 2
1
# 출력 2
3

🔍분석

👀 문제 유형 파악하기

1. 나열

먼저 나열해본다.

ex) n = 10

0	1	2	3	4	5	6	7	8	9	10
0	0	1	1	2	3	2	3	3	2	3

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)	1	2	3	…	n
최소 턴 개수

💡풀이

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]을 출력하면 된다