[백준]12852. 1로 만들기 2

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초

512 MB

15358

7117

5788

47.799%

문제

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

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

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

입력

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

출력

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

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

백준 실버1 DP문제입니다.

두개의 배열을 사용합니다.

arr[i]는 수 i를 1로 만들기 위한 연산의 횟수를 저장합니다.

ans[i]는 수 i를 1로 만들기 위한 첫번째 연산값을 저장합니다.

 

	#include<bits/stdc++.h>
	
	using namespace std;
	int arr[1000001];
	int ans[1000001];
	stack<int>st;
	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		memset(arr, 0, sizeof(arr));
		memset(ans, 0, sizeof(ans));
		arr[1] = 0;
		arr[2] = 1; ans[2] = 1;
		arr[3] = 1; ans[3] = 1;
		int n;
		cin >> n;
		if (n == 1) {
			cout << 0 << "\n";
			cout << 1;
			return 0;
		}
		if (n <= 3) {
			cout << arr[n] << "\n";
			cout << n << " " << 1;
			return 0;
		}
		for (int i = 4; i <= n; i++) {
			int a = INT_MAX, b = INT_MAX, c = INT_MAX;
			a = arr[i - 1] + 1;
			if (i % 2 == 0)
				b= (arr[i / 2] + 1);
			if (i % 3 == 0)
				c = (arr[i / 3] + 1);

			int temp = min(a, min(b, c));
			if (temp == a) {
				ans[i] = i - 1;
			}
			if (temp == b) {
				ans[i] = i / 2;
			}
			if (temp == c) {
				ans[i] = i / 3;
			}
			arr[i] = temp;
		}
		int k = n;

		cout << arr[n] << "\n";
		cout << n << " ";
		while (ans[k] != 1) {
			cout << ans[k] << " ";
			k = ans[k];
		}
		cout << 1;

	}

n=1,2,3 까지는 따로 처리해주고, n=4부터 횟수를 찾아야합니다

점화식은 다음과 같습니다.

arr[i]=min(arr[i-1]+1,min(arr[i/2]+1,arr[i/3]+1))

arr배열은 점화식으로 작성하고,

ans배열은 셋중 가장 작은값을 찾아서 연산값을 저장합니다.

예를들어 arr[i-1]+1이 가장 작으면 arr[i]에는 i-1 을,

arr[i/2]+1이면 arr[i]에 i/2, 그리고 arr[i/3]+1 이면 i/3을 저장합니다.