[백준] 1로 만들기

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

 

---

1. 문제 분석

 

연산을 사용하는 횟수의 최솟값을 출력. 즉 최적화 문제.

 

계속 3 또는 2로 나누면서 숫자를 더 많이 줄여나가면서 끝에 값을 도출하는 그리디한 접근은 불가능함. 문제에서 주어진 10의 예에서 볼 수 있듯이, 만약 그리디한 방식으로 접근할 경우

 

10 -> 5 -> 4 -> 2-> 1 의 총 네 번이 필요하지만, 최솟값의 경우

10 -> 9 -> 3 -> 1 로 세 번만에 만들 수 있음.

 

따라서, 모든 경우의 수를 살펴보는 완전 탐색을 채택.

 

2. 접근 아이디어

 

연산을 사용하여 최솟값을 도출하는 함수를 oper()라고 했을 때, 다음과 같이 수식화 할 수 있음.

 

oper(n) = min(oper(n / 3), oper(n / 2), oper(n - 1)) + 1

 

3. 완전 탐색 접근

 

def oper(n, cnt):
  if n == 1:
    return cnt
  
  cand1 = float('inf')
  cand2 = float('inf')
  cand3 = float('inf')
  
  if n % 3 == 0:
    cand3 = oper(n/3, cnt + 1)
  if n % 2 == 0:
    cand2 = oper(n/2, cnt + 1)
  cand1 = oper(n-1, cnt + 1)
  
  return min(cand1, cand2, cand3) + 1

 

cand1은, 1씩 감소하며 oper을 재귀하기 때문에 10의 6제곱에 달하는 n이 주어졌을 시 엄청난 연산을 중복 수행하게 됨. 즉, 문제에서 요구하는 0.15초 안에 들기에는 너무 빠듯함.

 

 

4. DP 접근

문제가 최적 부분 구조인가? 즉, 각 부분 문제를 최솟값으로 풀기만 하더라도 전체 문제의 최솟값을 구할 수 있는가? => yes.

 

 

위의 완전 탐색 코드를  메모이제이션 구현 레시피(https://sanghoonly.tistory.com/29)에 적용한, 큰 변화 없이 작성된 코드.

 

#include <iostream>
#include <memory.h>

#define MAX 1000001

using namespace std;

int cache[MAX];

int oper(int n)
{
  if (n == 1)
    return 0;
  if (cache[n] != -1)
    return cache[n];

  int &ret = cache[n];

  int cand1 = MAX, cand2 = MAX, cand3 = MAX;

  if (n % 3 == 0)
    cand3 = oper(n / 3);
  if (n % 2 == 0)
    cand2 = oper(n / 2);
  cand1 = oper(n - 1);

  // 최솟값 구하기
  int smaller = min(cand1, cand2);
  smaller = min(smaller, cand3);

  return ret = smaller + 1; // min(cand1, cand2, cand3) + 1이랑 똑같음
}

int main(void)
{
  int N;

  cin >> N;

  memset(cache, -1, sizeof(cache));

  cout << oper(N) << '\n';

  return 0;
}