[C/C++] 백준 - 1301번 : 비즈 공예

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

1301번: 비즈 공예

문제

다솜이는 자신의 목걸이를 구슬을 이용해서 만들려고 한다. 다솜이는 구슬을 N종류 가지고 있다. 서로 다른 종류의 구슬은 색이 다르다. 다솜이는 구슬을 실에 껴서 목걸이를 만들려고 한다. 무작정 껴도 상관없겠지만, 워낙 미적감각이 뛰어난 다솜이는 임의의 연속된 3개의 구슬의 색을 모두 다르게 하려고 한다.

예를 들어, 다솜이가 1번 구슬을 2개, 2번 구슬을 1개, 3번 구슬을 1개 가지고 있다고 하자. 1번 구슬이 초록, 2번 구슬이 파랑, 3번 구슬이 빨강이라고 하면, 연속된 3개의 구슬이 같은 색이면 안되기 때문에, 초록구슬을 반드시 목걸이의 끝에 있어야 한다. 따라서 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수는 초록-빨강-파랑-초록 또는 초록-파랑-빨강-초록 총 2가지이다.

반드시 가지고 있는 모든 구슬을 이용해야 하며, 목걸이는 원형이 아니라 직선이다. 다시말하면, 처음 구슬과 마지막 구슬은 이어져있는 것이 아니다.

다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 구하는 프로그램을 작성하시오.

 

---

 

연속된 3개의 구슬의 색을 다르게 하는 순서 경우의 수를 구하는 문제이다.

동적계획법으로 해결하는 것은 맞는데 어떻게 구현해야할까.

우리가 이용할 수 있는 정보는 각 자리에서 몇 개를 이용했는지, 해당 위치에서 전 구슬과 전전 구슬의 색깔은 무엇인지

위 정보들을 이용할 수 있다. 그럼 동적계획법으로 해결하기 위해 메모이제이션은 어떻게 적용해야할까 고민해야한다.

 

처음에는 위에서 언급한 것 모두

[현재까지 나열한 구슬의 개수][첫 번째 구슬 사용 개수][두 번째 구슬 사용 개수][세 번째][네 번째][다섯 번째][현재 바로 전 구슬의 색][현재의 전전 구슬의 색] 의 방식으로 구현하려했다.

 

하지만 이렇게 하게 되면 아무리 문제의 제한이 작더라도 메모리초과가 발생한다. 그래서 고민하던 차에 현재까지 나열한 구슬의 개수는 결국 -> 첫 번째 + 두 번째 + 세 번째 + 네 번째 + 다섯 번째 구슬의 수를 합친 값과 같다. 중복되는 정보를 저장한 방식이라는 것을 인식한 후 현재까지 나열한 구슬의 개수는 빼주었다.

 

이 문제의 제한이 "N은 3보다 크거나 같고, 5보다 작거나 같다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다. " 로 작기 때문에 위처럼 메모이제이션을 적용하더라도 통과가 가능하다.

 

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1234567
#define endl '\n'
#define ENDL cout << endl

using namespace std;

int N, sum;
vector<int> marble;
ll cache[10 + 1][10 + 1][10 + 1][10 + 1][10 + 1][5 + 1][5 + 1];

void input() {
	cin >> N;
	marble = vector<int>(6, 0);
	for (int i = 0; i < N; i++) {
		cin >> marble[i];
		sum += marble[i];
	}
}

ll path(int index, int curColor, int prevColor) {
	if (index == sum) return 1;
	ll& ret = cache[marble[0]][marble[1]][marble[2]][marble[3]][marble[4]][curColor][prevColor];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 0; i < N; i++) {
		if ((curColor != i && prevColor != i) && marble[i] != 0) {
			marble[i]--;

			ret += path(index + 1, i, curColor);

			marble[i]++;
		}
	}
	return ret;
}

ll solution() {
	memset(cache, -1, sizeof(cache));
	return path(0, 5, 5);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}