1로 만들기 백준 1463번 c++

문제

1로 만들기 1463

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;

int arr[1000005];
int x;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> x;
  arr[2] = 1; arr[3] = 1;
  for(int i = 4; i <= x; i++){
    arr[i] = arr[i-1]+1;
    if(i%3 == 0) arr[i] = min(arr[i], arr[i/3] + 1);
    if(i%2 == 0) arr[i] = min(arr[i], arr[i/2] + 1);
  }
  cout << arr[x];
}

리뷰

관찰이 필요한 DP문제다.

arr[i] = i를 1로 만들기 위해 필요한 연산 횟수의 최솟값

D[12]를 구할 때 어떤 과정인지, D[10]을 구할때 어떤 과정인지 구해보면 아이디어를 얻을 수 있었다.
3가지 연산 중에 최소 값을 찾아서 갱신해주면 된다.

1을 1로 만드는데 연산은 0번 필요하다. D[1] = 0
2를 1로 만드는데 연산은 1번 필요하다.(2로 나누거나 1을 빼기) D[2] = 1
이 문제에서는 D[1] 초기값만 정해주면 된다.

참고) 이 문제는 BFS로도 해결할 수 있다. dist 배열을 두고 초기값을 1로 한 뒤, x2, x3, +1로 뻗어나가면 답이 나온다.