📝 BOJ - 1로 만들기

thumbnail

문제

BOJ 1463번 : 1로 만들기

접근 방법

정수 NN이 주어질 때 이 NN에 다음의 연산을 가지고 11을 만드려고 할 때 연산을 사용하는 횟수의 최소값을 구하는 문제이다.

  • NN이 3으로 나누어 떨어지면, 3으로 나눈다.
  • NN이 2로 나누어 떨어지면, 2로 나눈다.
  • 1을 뺀다.

설명

현재에 집중해 숫자 66을 가지고 생각해보자! 66을 만들기 위해서는 22에 3을 곱하거나, 33에 2를 곱하거나, 55에 1을 더해야한다. 이제 22를 만들기 위해서는 11에 2를 곱하거나 1을 더해야한다. 3311에 3을 곱해 만들 수 있다. 5544에 1을 더해서 만들 수 있다.

위의 과정을 살펴보면 결국 어떤 숫자 NN을 만들기 위해서는 그 전의 숫자를 가지고 연산을 해야 한다. 즉, N1N-1에 1을 더하거나, N/2N/2에 2를 곱하거나, N/3N/3에 3을 곱해야한다. 그 전의 숫자에서의 연산의 합에 1을 더하여 3가지의 각각 다른 연산 횟수를 구할 수 있는데 그 중 최소값이 연산 횟수의 최소값이다.

결론

1부터 시작해 어떤 수 ii에 도달하기 위해서는 다음의 연산 중 하나를 해야 한다.

  • i1i-1에 1을 더한다.
  • ii가 2로 나누어떨어지는 경우, i/2i/2에 2를 곱한다.
  • ii가 3으로 나누어떨어지는 경우, i/3i/3에 3을 곱한다.

각 숫자의 연산하기 전의 숫자의 연산 횟수에 1을 더해서 3개의 연산 중 가장 적은 개수의 연산을 현재 숫자의 연산 횟수로 갱신하면 된다. 이를 점화식으로 나타내면 다음과 같다. 이 때 sum[i]sum[i]는 숫자 ii에 오기까지의 최소 연산횟수이다.

sum[i]=min(sum[i1],sum[i//2],sum[i//3])+1sum[i] = min(sum[i-1], sum[i//2], sum[i//3])+1

교훈

처음에 11부터가 아닌 NN부터 시작했다. 예를 들면 문제 예시에서 3이 되기 위해서는 4에서 1을 빼거나 6을 2로 나누거나 9를 3으로 나누거나 하면 된다. 할 수 있을 것 같긴한데 복잡해져서 포기했다ㅠㅠ

결국 Newmoon님의 풀이를 참고했는데 1부터 시작하는 것을 보았다. 사실 1에서 시작하든 NN에서 시작하든 똑같기 때문에 어느 걸 해도 상관없다. 동적계획법에서 항상 현재만 생각했는데 이제는 시작점도 고려해야겠다.

소스 코드

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])

👋@코딩하는펭귄
파이썬과 웹에 관심 많은 컴공 전공자

GitHubInstagram