[백준] 1로 만들기 1463번 파이썬 Python 다이나믹 프로그래밍

📌생각해보기

다이나믹 프로그래밍의 조건
1. problem이 sub-problem으로 쪼개질 때.
2. sub-problem으로 problem을 구할 수 있을 때.
3. sub-problem이 겹칠 때.(값을 보관해서 중복을 없앤다.)

1. 다이나믹 프로그래밍이므로 점화식으로 생각을 해야한다.
   15가 나오면 3으로 나눠볼까? X
   4가 나오면 2로 나눠볼까? X
   일단 1부터 10까지의 수를 나열해놓고 하나씩 넣어서 최소 횟수를 구해보고 값의 관계를 살펴볼까? O

2. 최단 횟수를 구해야하기 때문에 min( ?/3, ?/2, ?-1 )의 식을 활용할 수 있다.

3. 11일 경우를 생각해보자.
   4회: 11 - 1 = 10 -> -1을 하면 10이므로 10을 구한 것과 더하면 11을 구할 수 있다. (1+3)
   3회: 10 - 1 = 9 -> -1을 하면 9이므로 9를 구한 것과 더하면 10을 구할 수 있다. (1+2)
   2회: 9 / 3 = 3 -> 3으로 나누면 3이므로 3을 구한 것과 더하면 9를 구할 수 있다. (1+1)
   1회: 3 / 3 = 1 -> 3까지는 구할 수 있으므로 미리 구해준다. ( 1->0 / 2->1 / 3->1 )
   
   
   

📌내가 작성한 코드

import math
 
def solve():
    n = int(input())
    arr = [0, 0, 1, 1]
    
    for i in range(4, n+1):
        one, two, three = math.inf, math.inf, arr[i-1]

        if i % 3 == 0:
            one = arr[i//3]

        if i % 2 == 0:
            two = arr[i//2]

        value = 1 + min(one, two, three)     
        arr.append(value)
        
    print(arr[n])

solve()

📌풀이

1. 1 ~ 3까지는 직접 구할 수 있으므로 구해준다. (계산 횟수 단축)
   리스트는 0번째부터 시작이기에 0번째의 값은 아무거나 지정해준다.

arr = [0, 0, 1, 1]

2. for문을 생성한다. 앞에서 3까지는 미리 구해 놓았으므로 4부터 해당 수까지 구할 수 있도록 횟수를 정해준다.

for i in range(4, n+1):

3. 지문에서 제시한 %3, %2, -1의 값을 저장할 수 있는 변수를 지정해준다.
   one, two: %3, %2로 구한 값을 넣을 변수, math.inf로 초기화를 시켜놓는다. (math.inf를 쓰는 이유는 해당 변수가 다른 값으로 대체되지 않는 이상 다른 변수에 어떠한 큰 값이 들어와도 더 큰 수로 만들어 놓는 것)
   three: 만약 11이 들어왔을 경우, 2와 3으로 나누어 지지 않기 때문에 -1을 해야한다. -1을 한 계산 횟수 1을 나중에 더해줄 것이기 때문에 10을 구해야하는 것과 같으므로 처음부터 arr[i-1]을 해서 10으로 만들어준다.
   💡 math.inf: 어떠한 값보다 더 큰 수를 표현한 함수

	one, two, three = math.inf, math.inf, arr[i-1]

4. if문을 써서 만약 9가 3으로 딱 나누어 진다면, 나눠준다. 9를 3으로 나눈 계산 횟수 1은 나중에 더해 줄 것이다. 그리고 나눠서 나온 3의 값은 우리가 처음에 리스트에 넣어 놓것과 같이 1이므로 1이 변수에 들어간다.
   2로 나뉘어지는지 판별하는 if문 또한 같다.

	if i % 3 == 0:
            one = arr[i//3]
      
       	if i % 2 == 0:
            two = arr[i//2]

5. (11에서 -1한 계산 횟수 1) 또는 (9에서 3으로 나누었던 계산 횟수 1)을 여기서 더해준다.
   지문에서 최소 횟수를 구해야 한다고 했기 때문에 최소를 구할 수 있는 min() 함수를 사용해서 최소 횟수를 골라내고 거기서 +1을 해준다.
   (+1을 안해주는 것은 1 ~ 3번인데 앞에서 미리 값을 넣어놓았었다. arr = [0, 0, 1, 1])

	value = 1 + min(one, two, three)     
        arr.append(value)