1463번. 1로 만들기

첫번째 문제 풀이 전략

단순하게 생각함.
3 나누기, 2 나누기 , 1 빼기 에서 1로 만드는 것이므로,
3 나누기 > 2 나누기 > 1빼기 순으로 우선순위를 설정해서 진행을 함.
but 반례가 있음.
n 이 10일 경우에는 경우의 수가
가) 10 -> 9 -> 3 -> 1
나) 10 -> 5 -> 4 -> 2 -> 1

: 가)의 경우로 진행할때 최소의 횟수가 나오므로, 반례가 됨.
따라서 일반적으로 접근해서 풀수는 없음.

다이나믹 프로그래밍

: 가장 작은 값부터 시작해서 큰값까지 진행을 하는 알고리즘 방법.

이렇게 했을 때 왜 가능한 것이냐?
작은 거에서 최종 결과값을 구한 값이, 큰값에도 영향을 미치게 되므로,
반드시 타당한 값이 나옴.

• 푸는 방법에는 2가지가 있음.
  2번) 작은 것부터 진행해서 큰값까지 올라가는 for문으로 푸는 방법

• 이 문제에 빗대어서 생각을 해보면?
  점화식 : n을 1로 만들수 있는 최소 횟수를 구해라임.
  -> 이것을 역으로 뒤집어서 1 부터 시작해서 n으로 진행했을 때, 최소한의 횟수
  를 구해라로 생각할 수 있음.

• 경우의 수
  가) 10 -> 9 -> 3 -> 1
  나) 10 -> 5 -> 4 -> 2 -> 1
  다) 10 -> 5 -> 4 -> 3 -> 2 -> 1

여기서 3으로 만들수 있는 최소한의 횟수 : 1번.
여기서 4로 만들 수 있는 최소한의 횟수 : 2번.
이런식으로 진행해서 n까지 진행을 하면 되므로

• 결론 : 다이나믹 프로그래밍으로 접근 하면 됨.

코드

#include <iostream>
using namespace std;
#include <typeinfo>
#include <string>
#include <algorithm>

int dp[1000001];
// 3 : 15 ~ 
int main()
{
	int x;
	cin >> x;

	// 10 . 5 . 4 , 2  1
	// 10 . 9 . 3 . 1

	// x를 3가지 방법으로 연산을 했을때 나오는 최소 연산의 횟수
	// 를 d[x] 라고 하자. 

	// if( x == 1) 종료
	// 1번. if(x % 3 == 0) d[x] = dx[x / 3] + 1; 
	// 2번. if(x % 2 == 0) d[x] = dx[x / 2] + 1; 
	// 3번. d[x] = d[x - 1] + 1 
	// => + 1 의 의미는 횟수 1을 더한것을 의미함. 
	// 결과 : d[x] = min(dx[x / 3] + 1 , dx[x / 2] + 1 , d[x - 1] + 1);
	// d[x] = min(dx[x / 3] , dx[x / 2] , d[x - 1]) + 1로 나타낼 수 있음.
	
	// 점화식이 이렇게 나왔다고 해서, min 을 꼭 할 필요는 없음. 
	// 작은 것부터 큰 것까지 올라가자.

	// 10 에서 1을 만드는 경우는 어떻게 할 것인가?
	// 여기서 떠올릴수 있는 문제 풀이는?? 
	// : 큰 거에서 작은 문제로 나눠서 풀고 있음을 확인할 수 있음.
	// => 다이나믹 프로그래밍임. 
	// 1 에서 10을 만드는 경우와 동일함.

	dp[1] = 0;

	// 점화식 : x 를 만드는데 3가지를 이용했을 때
	// 최소한의 횟수를 구하는 것임. 
	// 여기서 x를 input까지 증가시키면서 확인을 하자. 
	for (int i = 2; i <= x; ++i)
	{
		dp[i] = dp[i - 1] + 1;

		if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
			dp[i] = dp[i / 2] + 1;
		if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)
			dp[i] = dp[i / 3] + 1;


	}


	cout << dp[x];

}