[01463] 1로 만들기

[01463] 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

코드

#include <iostream>
#include <cstring> //memset

using namespace std;

/* 조건 */
#define MAX_N 1000001

/* 변수 */
int N;
int memo[MAX_N];

/* 함수 */
int dp(int num, int cnt) {
    if(num == 1) return memo[1] < cnt? memo[1] + 1 : cnt + 1;
    int& ret = memo[num];
    if(memo[num] != -1 && cnt > memo[num]) return memo[num];
    if(num%6 == 0) return ret = min(dp(num/3, cnt+1), min(dp(num/2, cnt+1), dp(num-1, cnt+1))) + 1;
    if(num%3 == 0) return ret = min(dp(num/3, cnt+1), dp(num-1, cnt+1)) + 1;
    if(num%2 == 0) return ret = min(dp(num/2, cnt+1), dp(num-1, cnt+1)) + 1;
    return ret = dp(num-1, cnt+1) + 1;
}

int main() {
    /* 입력 */
    cin >> N;

    /* 풀이 */
    memset(memo, -1, sizeof(memo));

    /* 출력 */
    cout << dp(N, 0) << '\n';
}

풀이과정

논리

이번 문제는 딱히 논리라고 할 것은 없고 그대로 부딪혔다.
3으로 나눠지면 3으로 나눠보고, 2로 나눠지면 2로 나눠보고, 안되면 1을 빼고 count했다.
단, 시간제한이 있으므로 memoization으로 이미 계산한 값은 다시 계산하지 않았다.

그런데 풀고나서 정답을 찾아보니 bottom-top 형식으로 N까지 채워나가는 방식이 더 빨랐다...

함수

• dp(num, cnt)
  풀이를 담당하는 함수
  현재 이 함수를 몇번 호출했는지 count로 세어가며 memo[]를 업데이트 해주면서 해당 num에 대한 정답을 반환한다.
  1. 1에 도달했으면, 이미 구한 값보다 count가 작은지 확인 후 더 작은 값을 반환
  2. memo[num]에 이전에 구한 값이 저장되어 있고, 해당 값이 현재 진행되어 세어진 count보다 작으면 memo[num] 반환
  3. 3 또는 2로 나눠지는지 확인 후 3가지 경우 중 가장 작은 값 반환
• main()
  입력 받고, memo[]를 -1로 초기화 하고, 함수를 사용해 정답을 출력

출처

백준 [01463] 1로 만들기
https://www.acmicpc.net/problem/1463