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

문제

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

1463번: 1로 만들기

 

설명

 

이 문제는 DP로 풀 수 있다.

 

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정의하기

 

이 세가지 과정을 거쳐 문제를 풀 수 있다.

 

 

1. 테이블 정의하기
D[i]= i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

2. 점화식 찾기
D[12] =?

D[1]부터 D[11]까지의 값을 다 알고 있다고 가정하면
1, 2, 3, ..., 11을 1로 만들기 위한 최소 횟수를 다 알고 있다고 하면

이런 상황에서 D[12]를 구하는 방법은 12에서 할 수 있는 연산을 생각하면 된다.

D[4], D[6], D[11]을 이미 알고있다고 가정하면
3으로 나누거나 D[12] =D[4] +1
2로 나누거나 D[12] =D[6]+1
1을 빼거나 D[12]=D[11]+1
D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1) 이들 중에서 최솟값이 답이 된다.

 

3. 초기값 정의하기
D[1]=0

D 배열을 for문을 돌리면서 값을 채우면 된다.

 

코드

 

#include<iostream>
using namespace std;

int d[1000000];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  d[1] = 0; //초기값
  for(int i = 2; i <= n; i++){
    d[i] = d[i-1]+1;  //1을 뺐을때
    if(i%2 == 0) d[i] = min(d[i],d[i/2]+1); //2로 나누어졌을때
    if(i%3 == 0) d[i] = min(d[i],d[i/3]+1); //3으로 나누어졌을때
  }
  cout << d[n];
  return 0;
}