1로 만들기

문제

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

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

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

입력

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

예제 입력 및 출력

입력

10

 

출력

3

소스 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
int cache[1000001];

int count_op(int num) {
	int count;

	//기저사례
	if (cache[num] != -1)
		return cache[num];

	if (num == 1)
		return 0;

	cache[num] = 1;
	//재귀 호출
	count = count_op(num - 1); //1빼는 연산
	//2로 나누는 연산
	if (num % 2 == 0)
		count = min(count, count_op(num / 2));
	if (num % 3 == 0)
		count = min(count, count_op(num / 3));

	return cache[num] += count;
}

int main(void) {
	cin >> N;
	memset(cache, -1, sizeof(cache));
	cout << count_op(N);
}

문제 풀이

 1. cache 값 설정

• cache[num] -> 현재 값이 num일 때 1을 만드는데 필요한 연산의 최소 횟수

 2. 함수 탈출 조건

• num==1 일 때 완료되었으므로 0 반환

 3. 재귀 호출

• 함수가 호출되었을 때 num이 1이 아니면 1번의 연산은 무조건 하게 되므로 cache[num]=1로 초기화해준다.

• 1 빼주는 연산 : count_op(num-1)

• 2로 나누는 연산 : 숫자가 2로 나누어지면 count_op(num/2)

• 3으로 나누는 연산 : 숫자가 3으로 나누어지면 count_op(num/3)

• 위의 3가지 재귀 호출 함수의 반환 값 중 최솟값을 현재 cache값에 더하여 저장해준다.

 

문제 출처 : https://www.acmicpc.net/problem/1463