본문으로 바로가기

다이나믹 프로그래밍. 임의의 수를 줄여나가는 3가지 방법 중 최소 연산을 수행하는 방법을 택하되 중복되는 계산을 방지하기 위해 한 번 계산한 값은 배열에 미리 저장해놓는다.

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 1000000;

int dp[1000001];
int f(int);// 임의의 n을 1로 바꿀 때 최소 연산 횟수를 반환하는 함수

int main() {
  int n;
  scanf("%d", &n);
  printf("%d\n", f(n));
  return 0;
}

int f(int n) {
  if (n == 1) return 0;// 1이면 종료
  if (dp[n]) return dp[n];// 계산 중복 방지

  // 3으로 나누는 방법과 2로 나누는 방법과 1을 빼는 방법 중
  // 연산의 횟수가 최소인 방법을 구한다
  int x = MAX, y = MAX;
  if (n % 3 == 0) x = f(n/3)+1;
  if (n % 2 == 0) y = f(n/2)+1;
  return dp[n] = min(min(x, y), f(n-1)+1);// 한 번 구한 값은 dp에 저장
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 11727: 2xn 타일링 2  (0) 2018.05.15
[BOJ] 11726: 2xn 타일링  (0) 2018.05.15
[BOJ] 1463: 1로 만들기  (0) 2018.05.15
[BOJ] 11656: 접미사 배열  (0) 2018.05.14
[BOJ] 10824: 네 수  (0) 2018.05.14
[BOJ] 11655: ROT13  (0) 2018.05.14

댓글을 달아 주세요