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

문제

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

1463번: 1로 만들기

 

 

풀이

바텀-업 방식(동적 계획법 구현 방식)으로 구현 : 점화식을 이용해 DP 테이블을 채운다.

- count[i] : i에서 1로 만드는 데 걸리는 최소 연산 횟수

 

동적 계획법(Dynamic Programming) 알고리즘

동적 계획법(Dynamic Programming) 알고리즘

 

 

코드

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;

  int count[N + 1];
  count[0] = 0;
  for(int i = 1; i <= N; i++)
  {
    count[i] = i - 1;
    
    if(i % 3 == 0)
    {
      count[i] = min(count[i], count[i / 3] + 1);	// 나누기 3 연산
    }
    if(i % 2 == 0)
    {
      count[i] = min(count[i], count[i / 2] + 1);	// 나누기 2 연산
    }

    count[i] = min(count[i], count[i - 1] + 1);	// -1 연산 표현
  }

  cout << count[N];

}