[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 5928 KB, 시간: 4 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 21일 17:06:47

문제 설명

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

제출코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int arr[(int)1e6 + 1];
int main() {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	arr[1] = 0;
	arr[2] = 1;
	arr[3] = 1;

	int n;
	cin >> n;

	for (int i = 4; i <= n; i++)
	{
		arr[i] = arr[i - 1] + 1;

		//2 로 나누어진다면, 그에 따른 최솟값 비교 
		if (i % 2 == 0) {
			arr[i] = ((arr[i/2] + 1) < arr[i]) ? arr[i/2] + 1 : arr[i];
		}

		//3 ""
		if (i % 3 == 0) {
			arr[i] = ((arr[i/3] + 1) < arr[i]) ? arr[i/3] + 1 : arr[i];
		}
	}
	cout << arr[n];

	return 0;
}

설명

다이내믹 프로그래밍 문제이며 주어진 수 n을 1로 만들기 위한 최소 연산 횟수를 구하는 알고리즘이다.

처음에는 n숫자에서 바로 구할 생각을 하였으나, 큰 문제를 작은 문제로 쪼개서 해결하는 DP를 이용해 풀 수 있었다.

중요한것은 n을 바로 구할 생각을 하는것이 아니라 1부터 천천히 n까지 각각의 결괏값을 구하다보면 n이 구해진 다는 것이다. 상향식 기법인 것이다.

풀이

먼저 기초적인 값들은 설정해주었다. arr[1]은 아무 동작을 하지않으니 최솟값 0 arr[2],arr[3] 은 각각 2,3으로 한번에 나누어져서 1 을 설정하였다. arr[4] 부터 진행하게 된다.

기본적으로 i는 i-1과 1의 차이를 가진다. 기존의 i에서 -1하며 동작을 한번 하기 때문 -> arr[i] = arr[i-1] + 1 그 후 i가 2와 3으로 나누어질때의 경우와 비교해주어 최솟값을 arr[i]에 저장하는 것이다. 예를 들어 i가 6일때, 6/2 = 3 으로 한번 나눌때 한가지 동작을 취함으로 arr[i/2]와 arr[i]는 1의 차이를 가진다. arr[i] = arr[i/2] + 1 , 그리고 arr[i/2] = arr[3] 이므로 최솟값은 2일것이다.

아무튼 이런식으로 3가지 동작을 취하고 가장 최솟값을 arr배열에 저장함으로써 천천히 채워나가 n을 도달하게 되면,

arr[n]의 값을 출력할 수 있게된다.

느낀점

아직 DP가 많이 부족한거 같아서 다른 문제들을 많이 풀어봐야되겠다.