문제 링크
문제
티어: 골드 3
알고리즘: dp
다솜이는 자신의 목걸이를 구슬을 이용해서 만들려고 한다. 다솜이는 구슬을 N종류 가지고 있다. 서로 다른 종류의 구슬은 색이 다르다. 다솜이는 구슬을 실에 껴서 목걸이를 만들려고 한다. 무작정 껴도 상관없겠지만, 워낙 미적감각이 뛰어난 다솜이는 임의의 연속된 3개의 구슬의 색을 모두 다르게 하려고 한다.
예를 들어, 다솜이가 1번 구슬을 2개, 2번 구슬을 1개, 3번 구슬을 1개 가지고 있다고 하자. 1번 구슬이 초록, 2번 구슬이 파랑, 3번 구슬이 빨강이라고 하면, 연속된 3개의 구슬이 같은 색이면 안되기 때문에, 초록구슬을 반드시 목걸이의 끝에 있어야 한다. 따라서 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수는 초록-빨강-파랑-초록 또는 초록-파랑-빨강-초록 총 2가지이다.
반드시 가지고 있는 모든 구슬을 이용해야 하며, 목걸이는 원형이 아니라 직선이다. 다시말하면, 처음 구슬과 마지막 구슬은 이어져있는 것이 아니다.
다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, 둘째 줄에는 2번 구슬, 이런 형식이다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다.
출력
첫째 줄에 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 출력한다.
풀이
임의의 연속된 3개의 구슬의 색을 다르게 하면서 만들 수 있는 목걸이의 수를 구해야 한다.
일단 모든 경우의 수는 시간 초과로 구할 수 없기 때문에 메모제이션을 활용해서 이미 구한 값을 사용해야 한다.
현재 상태를 나타내기 위해서는 남은 구슬의 수가 필요하다.
그런데 남은 구슬의 수만 따지면 안된다. 임의의 연속된 3개의 구슬이라는 규칙이 있기 때문이다.
그래서 추가로 필요한 상태는 만들고 있는 목걸이의 마지막 구슬과 그 전 구슬이 무엇인지다.
예를 들어 1 2 3 종류의 구슬이 있다고 했을 때 (x?는 빈 줄을 의미한다.)
1 2 x1 x2 x3 x4 x5 이 상태에서
x1은 1과 2의 영향을 받고 (임의의 연속된 3개)
x2는 2의 영향을 받는다.
그래서 현재 상태에서 마지막 구슬과 그 전 구슬의 상태도 같이 포함해야 정확한 값을 얻을 수 있다.
위 풀이를 토대로 dp를 정의하면 7차원 배열이 된다. 다음과 같이 말이다.
dp[구슬의 종류][구슬의 종류][구슬1 개수][구슬2 개수][구슬3 개수][구슬4 개수][구슬5 개수]
이렇게 dp를 정의하고 나서 재귀함수를 구현하면 된다. 자세한 구현 방법은 코드를 참고하길 바란다.
이 풀이의 시간 복잡도는 O(6 6 11^5)정도 된다.
주의 할 점 답이 long형일 수 있음.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] beads = new int[6];
for(int i=1; i<=N; i++) {
beads[i] = Integer.parseInt(br.readLine());
}
long[][][][][][][] dp = new long[6][6][11][11][11][11][11];
ArrayList<Integer> list = new ArrayList<>();
System.out.println(answer(list, beads, dp));
}
static long answer(ArrayList<Integer> curList, int[] beads, long[][][][][][][] dp) {
for(int i=1; i<=5; i++) {
if(beads[i] == -1) {
return 0;
}
}
//현재 구슬 위치부터 -2까지 서로 다른 종류인지 체크 (3이면 1까지 3 2 1)
boolean[] visited = new boolean[6];
for(int i=curList.size() - 1; i>=(curList.size() - 1) - 2; i--) {
if(i >= 0) {
int ind = curList.get(i);
if(visited[ind]) {
return 0;
}
visited[ind] = true;
}
}
int lastInd = curList.size() - 1;
int bI1 = lastInd >= 0 ? curList.get(lastInd) : 0;
int bI2 = lastInd - 1 >= 0 ? curList.get(lastInd - 1) : 0;
if(dp[bI2][bI1][beads[1]][beads[2]][beads[3]][beads[4]][beads[5]] == -1) {
//-1이면 경우의 수가 없음을 의미
return 0;
}
if(dp[bI2][bI1][beads[1]][beads[2]][beads[3]][beads[4]][beads[5]] > 0) {
//0보다 크면 방문했고, 구해놓은 경우의 수를 반환
return dp[bI2][bI1][beads[1]][beads[2]][beads[3]][beads[4]][beads[5]];
}
//구슬을 전부 사용했고, 앞의 불가능한 경우의 해당하지 않는 경우
boolean isPosible = true;
for(int i=1; i<=5; i++) {
if(beads[i] > 0) {
isPosible = false;
}
}
if(isPosible) {
return 1;
}
//탐색
long result = 0;
for(int i=1; i<=5; i++) {
beads[i] -= 1;
curList.add(i);
result += answer(curList, beads, dp);
beads[i] += 1;
curList.remove(curList.size() - 1);
}
if(result == 0) {
dp[bI2][bI1][beads[1]][beads[2]][beads[3]][beads[4]][beads[5]] = -1;
} else {
dp[bI2][bI1][beads[1]][beads[2]][beads[3]][beads[4]][beads[5]] = result;
}
return result;
}
}