BOJ 1463. 1로 만들기

🙇‍♀️1로 만들기

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

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

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

예제 입력 1 
2

예제 출력 1 
1

예제 입력 2 
10

예제 출력 2 
3

🚀풀이

dp문제인데 어떻게 풀 지 감이 안잡혀서 어려웠다.
언뜻봤을 땐 3으로 나뉘면 가장 최소가 된다고 생각했는데 아니었다.

예를 들어서 17이면
17 -> 16 -> 8 -> 4 -> 3 -> 1
로 5번이 최소값인데 3으로 나뉘는 것을 고집하면
17 -> 16 -> 15 -> 5 -> 4 -> 3 -> 1
로 6번이 나온다.

이런 방식으로는 문제를 풀 수 없었다.
여러가지 가정을 다 생각하기엔 경우의 수가 너무 많았기 때문이다.

동적 계획법의 방법으로는 값을 기억해둘 cache를 만든다.
해결 방법은 간단했는데, 일단 cache[i]에는 cache[i - 1] + 1을 저장한다.
하지만 i % 3 == 0 이라면 cache[i]와 cache[i/3] + 1중 최소값으로 값을 저장한다.
마찬가지로 i % 2 == 0이라면 cache[i]와 cache[i/2] + 1중 최소값으로 값을 저장한다.

int N;
vector<int> cache;

void solve()
{
	cin >> N;
	cache = vector<int>(N + 1);

	cache[1] = 0; // 1일 때는 나눌 필요가 없으니까
	for (int i = 2; i <= N; ++i)
	{
		cache[i] = cache[i - 1] + 1;
		if (i % 3 == 0) 
			cache[i] = min(cache[i], cache[i / 3] + 1);
		if (i % 2 == 0)
			cache[i] = min(cache[i], cache[i / 2] + 1);
	}
	
	cout << cache[N];
}

동적 계획법은 적응이 안되네..

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> cache;

void solve()
{
	cin >> N;
	cache = vector<int>(N + 1);

	cache[1] = 0;
	for (int i = 2; i <= N; ++i)
	{
		cache[i] = cache[i - 1] + 1;
		if (i % 3 == 0)
			cache[i] = min(cache[i], cache[i / 3] + 1);
		if (i % 2 == 0)
			cache[i] = min(cache[i], cache[i / 2] + 1);
	}
	
	cout << cache[N];
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}