September 22, 2020
BOJ 1463번 : 1로 만들기
정수 이 주어질 때 이 에 다음의 연산을 가지고 을 만드려고 할 때 연산을 사용하는 횟수의 최소값을 구하는 문제이다.
현재
에 집중해 숫자 을 가지고 생각해보자! 을 만들기 위해서는 에 3을 곱하거나, 에 2를 곱하거나, 에 1을 더해야한다. 이제 를 만들기 위해서는 에 2를 곱하거나 1을 더해야한다. 은 에 3을 곱해 만들 수 있다. 는 에 1을 더해서 만들 수 있다.
위의 과정을 살펴보면 결국 어떤 숫자 을 만들기 위해서는 그 전의 숫자를 가지고 연산을 해야 한다. 즉, 에 1을 더하거나, 에 2를 곱하거나, 에 3을 곱해야한다. 그 전의 숫자에서의 연산의 합에 1을 더하여 3가지의 각각 다른 연산 횟수를 구할 수 있는데 그 중 최소값이 연산 횟수의 최소값이다.
1부터 시작해 어떤 수 에 도달하기 위해서는 다음의 연산 중 하나를 해야 한다.
각 숫자의 연산하기 전의 숫자의 연산 횟수에 1을 더해서 3개의 연산 중 가장 적은 개수의 연산을 현재 숫자의 연산 횟수로 갱신하면 된다. 이를 점화식으로 나타내면 다음과 같다. 이 때 는 숫자 에 오기까지의 최소 연산횟수이다.
처음에 부터가 아닌 부터 시작했다. 예를 들면 문제 예시에서 3이 되기 위해서는 4에서 1을 빼거나 6을 2로 나누거나 9를 3으로 나누거나 하면 된다. 할 수 있을 것 같긴한데 복잡해져서 포기했다ㅠㅠ
결국 Newmoon님의 풀이를 참고했는데 1부터 시작하는 것을 보았다. 사실 1에서 시작하든 에서 시작하든 똑같기 때문에 어느 걸 해도 상관없다. 동적계획법에서 항상 현재
만 생각했는데 이제는 시작점
도 고려해야겠다.
n = int(input())
table = [0] * (n+1)
for i in range(2, n+1):
table[i] = table[i-1]+1
if i%2 == 0:
table[i] = min(table[i], table[i//2]+1)
if i%3 == 0:
table[i] = min(table[i], table[i//3]+1)
print(table[-1])