[백준 알고리즘/Python] 1463 1로 만들기

문제

 

문제 이해

처음 DP를 만나서 어떻게 접근해야할지 몰랐습니다.메모이제이션 기법을 이용해야한다고 하는데 이전의 결과를 이용해야한다? 부터 어려웠습니다.

그림을 그려 살펴보니 이해가 되었습니다.

 

예를 들어 6이란 수를 1로 만들려면 

위 예시 에서 2,3으로 나눠지지 않는 결과는 제외했습니다.

ex) 5는 1빼는 방법밖에 없어서 4가 나왔습니다.

 

6에서 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법 이 3가지를 모두 적용할 수 있습니다.

1이 나오기 과정까지 2,3이 반복해서 나오는 것을 확인할 수 있습니다. 그럼 2,3의 값을 어디다가 저장해두고 다른 수를 찾아보면 되겠지요.

 

 

빈 리스트의 i가 1를 변화 시킬 때 수는 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법  중 가장 작은 수를 가지고 있는 것을 고르면 됩니다.

2부터 시작해서 i까지가면 2,3,4... 들은 1까지 가는 가장 작은 수를 들고 있게 하려면 배열에 호출된 횟수를 남겨주면 됩니다.

1을 빼는 방법을 하면 그 1을 뺀 배열 자리에 +1를 해야합니다.

ex) 

i가 4일 때 입니다. 4는 1로가기 위해서는 2번의 연산이 필요합니다. (2나누기 -> 1빼기,2나누기)

4-1 = 3이니 (3에서 1로가기 위한 연산 + 1)을 해야합니다.

그리고 4/2 = 2 (2에서 1로가기 위한 연산 + 1)을 해야합니다.

위 2개 중에 더 적게 1로가는 수를 찾으면 됩니다.

 

코드

num = int(input())
d = [0] * (num+1)

for i in range(2,num+1):
    #1을 뺀값 보다 작은게 없다면 뺀값이 그 숫자의 최선이다.
    d[i] = d[i-1] + 1 
    if(i % 2 == 0): #2로 나누어 질 때
        d[i] = min(d[i],d[i//2]+ 1) #ai = min(ai-1, a를 2로나눴을때) 검사
    if(i % 3 == 0): #3으로 나누어 질 때
        d[i] = min(d[i],d[i//3]+ 1) #ai = min(ai-1, a를 2로나눴을때 , a를 3로나눴을때) 검사

print(d[num])

2~찾기 위한 수를 d리스트에 저장하면서 값을 찾습니다.

 

-1의 값은 곧 1로 가기 위한 첫번 째 수입니다.

만약 2로 나눠진다면 더 적은 수로 1로 가기위한 수를 결정해야 합니다.

만약 3로 나눠진다면 더 적은 수로 1로 가기위한 수를 결정해야 합니다.

 

첫 번째 if문에서

위 연산을 하고

두 번째 if문에서 위와 같은 연산을 하는 것입니다.

2와 3, 둘다 나눠지는 수가 있기 때문입니다.