[BOJ][DP][실3][1463] 1로 만들기

문제 링크

1로 만들기/실3

첫 번째 풀이 : 다이나믹 프로그래밍, bottom-up

알고리즘

dp[i] : i를 1로 만드는 최소 횟수

for(i = 1...n)
  // i 번째에서 다음 번째의 값의 최소값을 찾는다.
  dp[i*3] = dp[i]+1
  dp[i*2] = dp[i]+1
  dp[i+1] = dp[i]+1
  처음 방문하는 경우는 그대로 대입.
  이미 방문한 경우 더 짧아지는 경우만 갱신.

정답 코드

#include <iostream>
using namespace std;

#define MAX 1000010
int dp[MAX];

int main(void) {
  int n = 0;
  cin >> n;

  dp[1] = 0;
  
  for (int i = 1; i <= n; i++) {
    if (i * 3 <= n) {
      if (dp[i * 3] == 0) {
        dp[i * 3] = dp[i] + 1;
      }
      else {
        dp[i * 3] = dp[i * 3] > dp[i] + 1 ? dp[i] + 1 : dp[i * 3];
      }
    }
    if (i * 2 <= n) {
      if (dp[i * 2] == 0) {
        dp[i * 2] = dp[i] + 1;
      }
      else {
        dp[i * 2] = dp[i * 2] > dp[i] + 1 ? dp[i] + 1 : dp[i * 2];
      }
    }
    if (i + 1 <= n) {
      if (dp[i + 1] == 0) {
        dp[i + 1] = dp[i] + 1;
      }
      else {
        dp[i + 1] = dp[i + 1] > dp[i] + 1 ? dp[i] + 1 : dp[i + 1];
      }
    }
  }
  cout << dp[n];

  return 0;
}

두 번째 풀이 : 다이나믹 프로그래밍, bottom-up 개선

알고리즘

dp[i] : i를 1로 만드는 최소 횟수

for(i = 1...n)
  // i 번째 값의 최소 값을 찾는다.
  dp[i] = dp[i-1] + 1;
  dp[i] > dp[i/3] + 1?
  dp[i] > dp[i/2] + 1?

Warning Notice: i에 대해서 dp[i]를 구하는 과정을 반복하기 때문에 if(i%2==0)을 해야 합니다. if(n%2==0)를 하면 안됩니다. if(i%2==0) 와 if(i%3==0)의 순서는 상관 없습니다.

정답 코드

#include <iostream>

#define MAX 1000010

using namespace std;

int dp[MAX];

int main(void) {
  int n = 0;
  cin >> n;

  dp[1] = 0;
  dp[2] = 1;
  dp[3] = 1;
  for (int i = 4; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    if (i % 2 == 0) {
      dp[i] = dp[i] > dp[i / 2] + 1 ? dp[i / 2] + 1 : dp[i];
    }
    if (i % 3 == 0) {
      dp[i] = dp[i] > dp[i / 3] + 1 ? dp[i / 3] + 1 : dp[i];
    }
  }

  cout << dp[n];
  return 0;
}

세 번째 풀이 : 다이나믹 프로그래밍, top-down

알고리즘

정답 코드

#include <iostream>
#include <algorithm>

#define MAX 1000010

using namespace std;

int dp[MAX];

int make_one(int n) {
  if (n == 1) return 0;
  
  if (dp[n] > 0) return dp[n];

  dp[n] = make_one(n-1)+ 1;
  if (n % 3 == 0) {
    dp[n] = dp[n] > make_one(n/3) + 1 ?  make_one(n/3) + 1 : dp[n];
  }
  if (n % 2 == 0) {
    dp[n] = dp[n] > make_one(n / 2) + 1 ? make_one(n / 2) + 1 : dp[n];
  }
  return dp[n];
}

int main(void) {
  int n = 0;
  cin >> n;

  cout << make_one(n);

  return 0;
}

결론

Success Notice: 다이나믹 프로그래밍의 쉬운 문제를 top-down, bottom-up 두 가지 방법으로 풀어봤습니다. 두 가지 모두 i에 대한 반복문에서 dp[i]를 구한다는 공통점이 있습니다. 수고하셨습니다.