[Python] Baekjoon 백준 1463번 1로 만들기

[Python] Baekjoon 백준 1463번 1로 만들기

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

 

코드

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

for i in range(4, n + 1):
    num[i] = num[i - 1] + 1

    if i % 3 == 0:
        num[i] = min(num[i // 3] + 1, num[i])

    if i % 2 == 0:
        num[i] = min(num[i // 2] + 1, num[i])

print(num[n])

반복문과 조건문으로 연산할때마다 카운트를 추가하는 방식으로 하였더니

시간초과 문제로 해결할수 없었다

 

문제 분류를 보면 "다이나믹 프로그래밍" 이다

구글에 검색해보면

- 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.

라고 되어있다.

과거에 구한 해를 활용한다면 메모이제이션을 적용하는것으로 보여진다

순차적으로 값을 구해가며 그 다음 값에 대해 앞에서 구한걸 활용하면 될것이다

 

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

확실하게 알수있는것으로

0과 1일때는 나눌것이 없으므로 0 일것이고

2와 3일때는 2 또는 3으로 한번만 나누면 되기에 1이다

그외의 숫자는 n + 1 까지 반복문으로 0으로 채워버렸다

 

for i in range(4, n + 1):
    num[i] = num[i - 1] + 1

0,1,2,3 까지는 값을 미리 넣어놨기에 4부터 반복문 시작하며

바로 전 수의 값에 +1을 해준다

이렇게 한 이유는 예를 들어 4 라면, 바로 전 수 3의 값은 1이다

그렇게 되면 3까지는 횟수를 구하였고 여기에 1을 더하는 과정 한번을 더하면 된다고 생각했다

이 값은 아직 확실한 값은 아니다

 

if i % 3 == 0:
	num[i] = min(num[i // 3] + 1, num[i])

if i % 2 == 0:
	num[i] = min(num[i // 2] + 1, num[i])

추가적으로 더 적은 횟수로 할수있는지 3또는 2로 나누어 0으로 떨어지는지 확인한다

3또는 2로 나누어 0으로 떨어진다면

그 나눈 몫이 이미 리스트에 있을것이고 거기에 +1한 값과

위에서 미리 입력한 값중에 적은 수를 다시 해당 인덱스 값으로 넣는다

 

3과 2의 if 문을 elif 로 하지 않은 이유는

3과 2가 같이 나누어 떨어지는 6, 12, 18, 24 등등... 같은 수들은

각각 계산한 값의 최소 횟수를 뽑아내기 위함이다

 

print(num[n])

그리고 쭉 저장된 리스트에서 입력받은 인덱스 n 에 대해 출력을 해준다

 

 

참고

동적 계획법 - 나무위키

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95