BOJ 1463 1로 만들기

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

 

 

- DP를 이용해서 푼 첫번째 문제.

- 점화식을 세우는 것이 중요하다!

- DP에서는 [ 재귀 또는 for문 ] 을 이용하여 문제 solve 가능

당연히 for문 이용한 것이 시간복잡도 적게 걸린다.

 

#include <cstdio>

int d[1000010];

int main(){
  int n;
  scanf("%d", &n);
  d[1]=0;
  for(int i=2; i<=n; i++){
    d[i] = d[i-1]+1;
    if(i%2==0 && d[i]>d[i/2]+1){
      d[i]=d[i/2]+1;
    }
    if(i%3==0 && d[i]>d[i/3]+1){
      d[i]=d[i/3]+1;
    }
  }
  printf("%d", d[n]);
  return 0;
}