백준 - 32462 Construct a coin set

 

해결과정 - 해 구하기

문제는 그리드 알고리즘 으로 1 ~ n-1원까지는 최적의 답을 찾지만 n원에서는 최적의 정답을 찾지 못하는 coin set를 찾아내라는 것이다

여기에서 그리드 알고리즘은 coin set이 주어진 경우 가장 금액이 높은 금액을 우선적으로 선택하는 알고리즘인데 예를 들어 n은 6이고 1 , 3, 4가 있을때 1 ~ n-1원 까지는 최적의 해를 계산하지만 6원인 경우 그리드 알고리즘은 4, 1 , 1원 최적의 해는 3, 3원으로 그리드 알고리즘이 최적의 정답을 찾아내지 못하게된다

 

처음 생각했던 방식은 2를 제외한 모든 수를 출력하는 것이다 이 방식이 해가 되는 이유는 n 일때 1, 3, 4 ... n - 2로 해를 구성하면 위의 예제와 같은 이유로 n 일 경우에만 최적의 정답이 아니게 된다 하지만 이렇게 푼다면 출력초과가 발생하는 문제가 생겨 다른 해결책이 필요하였다

 

최종 해결방안은 짝수와 홀수를 나누어서 생각하는 것이였다

짝수일 경우 n이 최적의 해가 되지 않기위해 1, n/2, n - 2가 존재하면 그리드는 반드시 3개 이상의 coin을 가지고 최적의 해를 2개의 coin이 된다 여기에서 1 ~ n - 1은 최적의 해를 가지고 있는 이유는 n - 1일경우는 2개 n - 2 이하는 0 개이 거나  그수와 1로 이루어진 coin 셋이 해가 되기 때문이다

 

홀수일 경우는 2가 없으면 된다 라는 것에서 유래된 해인데 n 일경우  n - 2의 코인을 선택한 뒤에  1, 1의 코인을 선택해야 되는데 최적의 해는 n - 3의 코인과 3을 선택하는 것이다  나머지 경우는 짝수와 같은 이유로 최적의 해를 선택한다

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<queue>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

typedef long long ll;

int main() {
	Fast;

	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int n;
		cin >> n;
		
		if (n <= 5) {
			cout << -1 << '\n';
			continue;
		}

		if (n % 2 == 0) {
			cout << 3 << '\n';
			cout << 1 << " " <<  n / 2 << " " << n - 2 << '\n';
		}
		else {
			cout << 4 << '\n';
			cout << 1 << " " << 3 << " " << n - 3 << " " << n - 2 << '\n';
		}
	}
	

	return 0;
	
}

 

후기

짝수먼저 생각하여 짝수와 홀수를 나누었는데 지금생각해보니 그냥 홀수 방식으로 짝수도 6을 제외하고 해결이 된다