JArchive 프로그래밍 일기

문제

1로 만들기2 백준 12852

"맞았습니다"코드

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

int D[1000002];
int n;

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

  cin >> n;

  D[1] = 0;
  D[2] = D[3] = 1;

  for(int i = 4; i <= n; i++) D[i] = 1e9;

  for(int i = 4; i <= n; i++){
    if(i % 3 == 0) D[i] = min(D[i/3] + 1, D[i]);
    if(i % 2 == 0) D[i] = min(D[i/2] + 1, D[i]);
    D[i] = min(D[i-1] + 1, D[i]);
  }

  cout << D[n] << '\n';

  while(1){
    cout << n << ' ';
    if(n == 1) break;
    if(n % 3 == 0 && (D[n/3] + 1) == D[n]) n /= 3;
    else if(n % 2 == 0 && (D[n/2] + 1) == D[n]) n /= 2;
    else n--;
  }
  return 0;
}

리뷰

bfs로 풀어야하나? 싶었다.
9를 3으로 나누는 연산을 하면, D[9] = D[3] + 1 임을 적어보니까.
1을 만드는 '가장 적은 횟수'를 메모이제이션 하는 dp 같았다.

주어진 숫자에서 1을 만드는게 아니라, 1에서 주어진 숫자로 갈 때 최소 연산 횟수를 찾는 반복문을 만들었다.

최소 연산 횟수를 찾는거니까, 메모이제이션 배열 D는 큰 수로 초기화 해뒀다.