53. Python 백준 1463 번 자세한 설명

안녕하세요. 코딩하는 덕구입니다. Python 백준 1463 번 1로 만들기 입니다.

다이나믹 프로그래밍 문제입니다.

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

예를들어 숫자 10을 연산 1, 2, 3 번을 이용해 1을 만든다고 하면

10 -1, = 9

9/3 = 3

3/3 = 1 

3단계로 연산할 수 있습니다.

이때 9에서 연산들을 이용하여 1로 가는 횟수

3에서 연산들을 이용하여 1로 가는 최소 횟수 등이 필요하게 되죠

결국 입력값보다 작은수부터 연산 최소 횟수를 구해서 저장하면

큰 수에서 최소값을 찾기 위해 모든 경우의 수를 구해서 비교 하는게 아닌

반복되고 불필요한 연산횟수를 줄일 수 있습니다. 

 

어떤 숫자의 최소 연산을 계산할 때 3가지의 경우가 있습니다.

1. 1을 빼주면 미리 계산했던 값이 나오는 경우

2. 2로 나눠지는 경우

3. 3으로 나눠지는 경우

이 3가지의 경우 중 어떤 값이 최솟값인지 모르기 때문에 직접 계산을 해서 가장 작은 값을 해당 cnt 의 index에

넣어주면 됩니다. 

 

배열의 index를 각 숫자로, 내용을 최소 연산 횟수로 저장할 배열(리스트) cnt를 선언하고, 

0, 1, 2, 3 의 경우에 필요한 연산 횟수를 기본값으로 넣어놓습니다. 

cnt = [0, 0, 1, 1] + [0 for _ in range(4, N+1)]

0의 경우는 중요하지 않으므로 아무 숫자나 넣습니다.

1 은 연산하지 않아도 1이므로 0,

2는 2-1=1 혹은 2/2=1, 1회가 필요하므로 1

3은 3/3 = 1, 1 회가 필요하므로 1입니다.

4부터는 입력 값에 따라 배열의 공간만 미리 설정을 해줍니다.

 

for i in range(4, N+1):
    cnt[i] = cnt[i-1] + 1 #바로 전 수에 cnt += 1 최소값인지는 확실하지 않음

1, 2, 3 의 경우에 미리 값을 구해서 저장했기 때문에

for문을 4부터 시작하여 숫자 4의 경우를 계산해서 저장해봅시다.

먼저 1번째 경우인 -1의 경우를 계산해서 넣습니다.

바로 전 수의 최소 연산 횟수에 -1을 했으므로 바로 전 수에 +1 을 하면 최소 연산이겠죠.

이 값을 일단 저장합니다.

 

if i % 3 == 0:
    cnt[i] = min(cnt[i//3] + 1, cnt[i]) #3으로 나눈 수가 방금 계산한 수 보다 더 작다면 최소값 업데이트
if i % 2 == 0:
    cnt[i] = min(cnt[i//2] + 1, cnt[i]) #2으로 나눈 수가 방금 계산한 수 보다 더 작다면 최소값 업데이트

2, 3번의 경우입니다. 2나 3으로 나눠지면 나누고, 연산횟수를 1 카운트 합니다.

이 경우 처음 연산과 3으로 나눈 연산 중 더 작은 값이 최소값으로 업데이트 됩니다.

두번째 if 문에서도 첫번째 if문을 통해 나온 최소값과, 2 로 나눠진 수의 최솟값을 비교해서 업데이트 합니다.

 

최종적으로 cnt[i]는 숫자 i를 1로 만들기 위한 최소값이 들어있게 됩니다.

print(cnt[N])

이것을 출력하면 정답이 되겠죠.

 

백준 1463번 Python 최종 코드입니다.

N = int(input())
cnt = [0, 0, 1, 1] + [0 for _ in range(4, N+1)]

for i in range(4, N+1):
    cnt[i] = cnt[i-1] + 1 #바로 전 수에 cnt += 1 최소값인지는 확실하지 않음

    if i % 3 == 0:
        cnt[i] = min(cnt[i//3] + 1, cnt[i]) #3으로 나눈 수가 방금 계산한 수 보다 더 작다면 최소값 업데이트
    if i % 2 == 0:
        cnt[i] = min(cnt[i//2] + 1, cnt[i]) #2으로 나눈 수가 방금 계산한 수 보다 더 작다면 최소값 업데이트

print(cnt[N])

 

Python 백준 1463 번 이였습니다. 감사합니다.