[BAEKJOON] 1415번 사탕

https://www.acmicpc.net/problem/1415

1415번: 사탕

문제조건

1. 사탕의 개수 : n개
2. 사탕 가격의 합이 소수
3. 모양이 똑같은 방법은 사지 않는다.

제일 먼저 떠오른 생각은 집합이었다.

집합이 한번 나오면 모양이 똑같은 방법을 커버할 수 있고, 그 집합의 원소들의 합이 소수가 되면 되기 때문이다.

 

라고 생각했지만 도저히 이 방법으로는 풀리지 않을 것 같았다,,,

 

일단 로직에 대해서는 더 고민해보기로 하고 소수 구하는 알고리즘을 보겠다.

 

void isPrime() {
	prime[0] = prime[1] = false;
	//전부 소수라고 초기화
	for (int i = 2; i <= MAX; i++) {
		prime[i] = true;
	}
	//각 배수로 나뉘어지면 false로 바꿈
	for (int i = 2; i*i <= MAX; i++) {
		if (!prime[i]) continue;
		for (int j = i * i; j < MAX; j += i) {
			prime[j] = false;
		}
	}
}

숫자가 크면 클수록 판단하는데 for문을 두번돌면서 n^2인 시간복잡도가 매우 높아질 것이기 때문에, 이 복잡도를 낮추기 위해서, i*i까지만 for문이 돌도록 해줬다. n이하의 소수를 구하는데, √n까지만 구하고, 그 이후의 배수는 n을 넘어 가기때문에 계산과정 자체가 의미없기 때문이다.

위의 계산방법을 에라토스테네스의 체 라고 한다.

 

이렇게 에라토스테네스의 체를 구현하고 보니 어차피 판단은 prime 배열로 해주면 되고, 그러면 내가 구해야 할것은,  모든 경우의 수의 가격이다,,! DP로 풀란소리다,,,,,,

 

일단 DP로 접근해보기 위해서 점화식을 생각해봤다. 꽤 많이 ㅎㅎ,,

점심 나가서 먹을것 같다 ㅎㅎ

 

정말 까다로운 문제인게 우선 dp이므로 숫자가 엄청 커질것에 대한 대비를 못했다. int 범위가 대략 21만까지 인데 dp배열의 최대 길이만 50만이므로, long long으로 바꿔주었다.

dp[n] : 사탕 가격의 합이 n원일 때 주어진 사탕 가격에서의 모든 경우의 수
dp[i] = dp[i] + ∑ dp[i - 각각 사탕가격 * 사탕개수]) (1 <= 사탕개수 <= 총 사탕개수)

 

이를 구현하면 삼중 for문으로 머리가 터지는 줄 알았다,,,,,

단순하게 생각하면, n원 이하의 가격에서 모든 종류의 사탕을 개수별로 빼준것을 하나씩 더 해주면 n원에서의 모든 경우의 수가 top-down approach로 계산된다. 따라서 우리는 특정하게 값을 모르더라도 초반 dp값 하나만 입력해주면, 계산이 자동으로 된다는 것이다.

그리고 가격이 0인 사탕의 경우를 입력을 받을때부터 따로 카운트해서 0의 개수 + 1 만큼만 곱해줬다. 이러면 뭔가 로직이 깔끔하게 정리 된것 같다.

 

#include <iostream>
#include <vector>
#define MAX 500001
using namespace std;
bool prime[MAX];
int n;

//first : 사탕 가격, second : 같은 가격 사탕개수
vector<pair<int, int> > v;
//n원일 때 주어진 입력에서의 모든 경우의 수
long long dp[MAX], answer;


// n종류 사탕, 사탕 가격의 합 = 소수
void isPrime() {
	prime[0] = prime[1] = false;
	//전부 소수라고 초기화
	for (int i = 2; i < MAX; i++) {
		prime[i] = true;
	}
	//각 배수로 나뉘어지면 false로 바꿈
	for (int i = 2; i*i <= MAX; i++) {
		if (!prime[i]) continue;
		for (int j = i * i; j < MAX; j += i) {
			prime[j] = false;
		}
	}
}

int main(){
	cin >> n;
	int cnt = 1;
	for (int i = 0; i < n; i++) {
		int num = -1;
		int a;
		cin >> a;
		if (a == 0) {
			cnt++;
			continue;
		}
		for (int i = 0; i < v.size(); i++) {
			if (a == v[i].first) {
				num = i;
				break;
			}
		}
		if (num == -1) v.push_back({ a,1 });
		else v[num].second++;
	}
	//소수찾기 끝
	isPrime();
	dp[0] = 1;

	for (pair<int,int> a : v) {
		for (int i = MAX; i >= 0; i--) {
			for (int j = 1; j <= a.second; j++) {
				if (i - a.first * j < 0) break;
				dp[i] += dp[i - a.first * j];
			}
		}
	}

	for (int i = 2; i <= MAX; i++)
		if (prime[i])
			answer += dp[i];
	cout << answer * cnt;
}

진짜 어려웠다,,,