백준 1463 - 1로 만들기

문제 번호: 1463

문제 제목: 1로 만들기

문제 주소: https://www.acmicpc.net/problem/1463

문제 내용

아래 세 가지 규칙을 바탁으로 X를 1로 만드는데 필요한 최소한의 연산 횟수를 출력한다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

테스트 케이스

2	1
10	3
10000	14

문제 풀이

일정 범위까지 점화식을 만들고 점화식을 바탕으로 아래의 내용에 대해 판단한다.
1. m1, m2, m3 변수를 만들고 100만보다 큰 수로 초기화 한다.
2. n % 3 == 0인 경우 [n / 3]의 값을 구해 m1에 저장한다.
3. n % 2 == 0인 경우 [n / 2]의 값을 구해 m2에 저장한다.
4. [n - 1]의 값을 구해 m3에 저장한다.
5. m1, m2, m3의 값을 비교해 가장 작은 값 + 1을 [n]에 저장한다.
6. 1~5를 반복한다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1463()
{
	int N;
	cin >> N;
	int* count = new int[N + 1];
	count[0] = 0;
	count[1] = 0;
	for (int i = 2; i <= N; i++)
	{
		int d3 = 1000001;
		int d2 = 1000001;
		int m1 = 1000001;
		if (i % 3 == 0)
		{
			d3 = 1 + count[i / 3];
		}
		if (i % 2 == 0)
		{
			d2 = 1 + count[i / 2];
		}
		m1 = 1 + count[i - 1];
		count[i] = d3 < d2 ? d3 : d2;
		count[i] = count[i] < m1 ? count[i] : m1;
	}
	cout << count[N] << endl;
	delete[] count;
	return;
}