[백준 / BOJ] C++ 1463 1로 만들기

1463번: 1로 만들기

 

문제

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

1463번: 1로 만들기

 

 

풀이

다이나믹 프로그래밍(DP)으로 해결할 수 있는 문제다. 할 수 있는 연산은 아래와 같다.

1. 3으로 나누어 떨어지면 3으로 나누기
2. 2로 나누어떨어지면 2로 나누기
3. 1 빼기

bottom-up 방식으로 구현했다. 1은 0번의 연산으로 1을 만들 수 있다. 2 이상의 수는 기본적으로 i번째 수는 이전 수에서 1을 더한 수이므로 dp[i] = dp[i-1] + 1이다.

 

만약, i번째 수가 3의 배수라면 i/3에서 3을 곱한 수일 것이다. 따라서 dp[i] = dp[i/3] + 1일 '수' 있다. '수'인 이유는 i/3에서 3을 곱한 것보다 i-1에서 1을 더한 경우가 더 빠를 수도 있기 때문이다. 2의 배수일 때도 이와 마찬가지로 작성하면 된다.

 

dp배열을 모두 구했다면 dp[n]을 출력해 n이 0이 될 수 있는 가장 빠른 횟수를 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> dp(n + 1);
  dp[1] = 0;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    if (!(i % 3))
      dp[i] = min(dp[i], dp[i / 3] + 1);
    if (!(i % 2))
      dp[i] = min(dp[i], dp[i / 2] + 1);
  }
  cout << dp[n];
  return 0;
}