[백준 C++] 1463 1로 만들기

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

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

풀이

제한시간이 0.15초이므로, 반복되는 구조를 이용해서 시간을 단축해야한다.
문제가 단조로운편이므로 DP나 그래프탐색등으로 풀수있는데 필자는
DP - top-down으로 풀었다.
보통 bottom -up이 편할것같은데
코드상으론 top-down이 간결한것같다.

이 문제는 크게 3가지경우인데, 사실은 4가지경우가 될수도있다.

• x가 2로 나뉘어떨어지면 DP(x) = DP(x / 2) + 1
  연산을 1회했으니 + 1을해준다.
• x 가 3으로 나뉘어떨어지면 DP(x) = DP(x / 3) + 1
• 위 두 경우가아니면 DP(x) = DP(x - 1) + 1
• x가 2와 3둘다 나뉘어떨어지는경우

문제는 마지막경우때문에, 문제에서 최적의 연산횟수를 출력해야하니,
2로나뉜결과 3으로나뉜결과 -1만 한결과 이 세가지중 최적의값을 dp에 저장해야한다.
이제 구현해보자.

0. 메모이제이션을 활용하기위해 dp를 선언한다. 이때 dp[0] = -1 인데
   이후에 X = 1 일때 다른값이 출력되길래 맞추기위해 넣은값이다.
   (어쨋든 문제에선 -1 인덱스의 값을 참조하게되므로 DP(1)은 DP(0) 을 참고 하게되므로.. )
   dp값이 존재하면 그값을 출력한다.(메모이제이션)

1. 2와 3동시에 나누어 떨어지는경우

아래에 설명할 2,3,4번결과중 최솟값으로 적는다.

2. 2로 나뉘어 떨어지는경우:

2로 나눌수도있고, 그냥 -1을 뺄수도있다. (문제의 핵심.)
둘중 최솟값을 dp에 기록
무조건 2로 나누어야할 필요는 없는것.
-1을 하는 경우는 생각을 좀 해봐야겠다...

3. 3으로 나뉘어 떨어지는 경우

3으로 나누거나 -1을 빼는경우중 최솟값을 dp에 기록.

4. -1 하는 경우

연산횟수는 +1이다.

5. 위 조건에서 구한 dp값을 출력하여 마무리

이제 X를 입력받아서 DP(X)를 출력하면된다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define len(x) x.length()
#define sz(x) ((int)x.size())
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
//#define MAX 
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill;
_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int X;
int dp[1000001];
void init();
void func();

void init() {
	sc("%d", &X);
	dp[0] = -1;
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
}

int DP(int x) {
	if (dp[x])
		return dp[x];

	
	if(x % 2 == 0 && x % 3 == 0)
		dp[x] = min(min(1 + DP(x / 2), 1 + DP(x / 3)), 1 + DP(x - 1));
	else if (x % 2 == 0)
		dp[x] = min(1 + DP(x - 1), 1 + DP(x / 2));
	else if (x % 3 == 0)
		dp[x] = min(1 + DP(x - 1), 1 + DP(x / 3));
	else
		dp[x] = 1 + DP(x - 1);

	return dp[x];
}

void func() {
	//DEBUG
	pr("%d", DP(X));
}

int main(void) {
	init();
	func();

	rt 0;
}