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는 큰 수로 초기화 해뒀다.

문제

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로 뻗어나가면 답이 나온다.