백준 1301 비즈 공예 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/1301

1301번: 비즈 공예

문제

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

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

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

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

입력

첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, 둘째 줄에는 2번 구슬, 이런 형식이다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다.

출력

첫째 줄에 다솜이가 목걸이를 만들 수 있는 방법의 경우의 수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

7차원 dp로 해결할 수 있는 문제다.

7차원인 이유는 이전 구슬의 번호, 전전 구슬의 번호와 구슬의 종류가 3~5개로 정해져 있으므로 최대 크기인 5를 사용하여 총 7차원 배열을 사용했다.

dp[a][b][c][d][e][f][g] = 각 구슬A,B,C,D,E의 남은 개수가 a,b,c,d,e이고 전전 구슬의 번호가 f, 이전 구슬의 번호가 g인 경우의 수

이 dp 배열을 이용해 재귀 함수 호출의 수를 줄인다. 즉 메모이제이션으로 a,b,c,d,e,f,g일 때의 경우의 수를 저장해 놓고 이를 다시 계산할 필요 없이 갖다 쓰는 것이다.

    if(a==0 && b==0 && c==0 && d==0 && e==0) return 1
    var ret:Long = dp[a][b][c][d][e][f][g]
    if(ret != -1L) return ret
    ret = 0
    for(i in 1 .. 5){
        if(f != i && g != i && beads[i] >0){
            beads[i]--
            ret += makeDp(beads,g,i)
            beads[i]++
        }
    }
    dp[a][b][c][d][e][f][g] = ret
    return ret

핵심 코드이다.

- A,B,C,D,E를 모두 사용했으면 1을 리턴

- a,b,c,d,e,f,g일때 경우의 수를 이미 알고 있다면 그 경우의 수를 리턴하고 아니면 계산한다.

- A,B,C,D,E 구슬 중 넣을 수 있는 구슬을 모두 넣어본다.

- dp배열에 계산한 값을 넣어준다.(다음에 같은 a,b,c,d,e,f,g를 방문하게 된다면 이 값을 사용)

- 재귀적으로 계산한 경우의 수 합을 리턴한다. (재귀 함수 호출 트리를 생각하면 루트 노드의 리턴 값이 정답이 된다.)

- 굳이 dp를 -1로 초기화한 이유는 A,B,C,D,E 구슬을 넣어 경우의 수를 계산한 게 0이 나올 수 있기 때문에 이미 계산을 마쳤지만

if(ret != 0L) return ret 의 조건에 걸리지 않아 가지치기가 제대로 되지 않기 때문이다.

 

코드

val br = System.`in`.bufferedReader()
fun getInt() = br.readLine().toInt()
val dp = Array(11) { Array(11) { Array(11) { Array(11) { Array(11) { Array(6) { LongArray(6){-1} } } } } } }
// f = 전전
// g = 전
fun makeDp(beads: IntArray, f: Int, g: Int) : Long{
    val a = beads[1]
    val b = beads[2]
    val c = beads[3]
    val d = beads[4]
    val e = beads[5]
    if(a==0 && b==0 && c==0 && d==0 && e==0) return 1
    var ret:Long = dp[a][b][c][d][e][f][g]
    if(ret != -1L) return ret
    ret = 0
    for(i in 1 .. 5){
        if(f != i && g != i && beads[i] >0){
            beads[i]--
            ret += makeDp(beads,g,i)
            beads[i]++
        }
    }
    dp[a][b][c][d][e][f][g] = ret
    return ret
}

fun main() = with(System.out.bufferedWriter()) {
    val n = getInt()
    val beads = IntArray(6)
    for(i in 1 .. n){
        beads[i] = getInt()
    }
    write("${makeDp(beads,0,0)}")
    close()
}