[알고리즘] 1로 만들기 - 백준 1463

문제

 

 

풀이

이 문제는 최솟값을 구하기 위해 비교해야 하는 경우의 수가 N / 3, N / 2, N - 1로 세개이다.

N의 최솟값은 위의 연산에 한 번의 연산이 추가된 것 이므로 N / 3, N / 2, N - 1중 최솟값에 1을 더하는 것으로 N의 최솟값을 구할 수 있을 것 같다. 

N의 최솟값을 배열의 N번 배열에 저장한다고 하면 점화식을 쉽게 구할 수 있다.

 

따라서 내가 생각한 점화식은

min(min(arr[N / 3], arr[N / 2]), arr[N - 1]) + 1이다.

 

오답이다. 

아마 나누어 떨어지지 않아도 N / 3, N / 2를 점화식에 포함해서 그런 것 같다. 

나누는 수를 반영하는 경우는 조건문으로 검사해야 할 것 같다.

 

N - 1은 항상 점화식에 포함시키고 

N / 3, N / 3는 나누어 떨어지는 경우만 포함시킨다. 

그렇가면 점화식이 이렇게 된다.

if (i % 3 == 0) minCnt = min(minCnt, arr[i / 3]);
if (i % 2 == 0) minCnt = min(minCnt, arr[i / 2]);
minCnt = min(minCnt, arr[i - 1]);

 

 

 

코드

#include<iostream>
using namespace std;

int arr[1000001], n;

int main()
{
	cin >> n;

	for(int i = 2; i <= n; i++)
	{
		int minCnt = INT_MAX;

		if (i % 3 == 0) 
			minCnt = min(minCnt, arr[i / 3]);
		if (i % 2 == 0) 
			minCnt = min(minCnt, arr[i / 2]);
		minCnt = min(minCnt, arr[i - 1]);
			
		arr[i] = minCnt + 1;
	}

	cout << arr[n];
}