백준 12969 ABC Kotlin (dp)

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

12969번: ABC

문제

정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오.

• 문자열 S의 길이는 N이고, 'A', 'B', 'C'로 이루어져 있다.
• 문자열 S에는 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍이 K개가 있다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 30, 0 ≤ K ≤ N(N-1)/2)

출력

첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

2022.07.21 - [알고리즘 문제 풀이/백준] - 백준 14238 출근 기록 Kotlin (dp)

2022.07.16 - [알고리즘 문제 풀이/백준] - 백준 1301 비즈 공예 Kotlin (dp)

이전 문제들과 비슷한 재귀에 DP를 사용하여 가지치기하는 유형이다.

Pair(짝)의 수를 cnt라고 하고

앞에 나온 A의 개수는 a

앞에 나온 B의 개수는 b

앞에 나온 C의 개수는 c

라고 한다.

 

우선 B가 오는 경우는 앞에 있는 A의 수만큼 cnt가 증가한다.

따라서 B가 올 수 있는 경우는 cnt + a가 K보다 작거나 같을 때이다.

C가 오는 경우는 앞에 있는 A의 수 + B의 수만큼 cnt가 증가한다.

따라서 C가 올 수 있는 경우는 cnt + a + b가 K보다 작거나 같을 때이다.

A는 위의 조건과 상관없이 올 수 있다.

위 조건에선 A와 B의 개수가 중요하다.

따라서 dp[a][b] = true/false라는 배열을 두면

A의 개수가 a이고 B의 갯수가 b일 때의 경우를 탐색했는지 안 했는지 알 수 있다.

하지만 이렇게 2차원 dp를 사용하면

AB

BA

같은 경우엔 둘 다 dp[1][1]이기 때문에 BA인 경우도 탐색해 주어야 하지만 패스하게 된다.

따라서 dp[a][b][c][cnt] = true/false라는 4차원 dp가 필요하다.

위 배열의 의미는 A의 개수가 a, B의 갯수가 b, C의 갯수가 c, 짝의 수가 cnt인 경우를 탐색했는지 안 했는지이다.

이 배열을 이용해 재귀 함수를 가지치기할 수 있다.

 

정답의 조건은 cnt가 K개가 나오면서 현재까지 사용한 알파벳의 길이가 N과 같아야 한다.

해당 조건을 만족하면 isFinish 플래그를 true로 두고 더 이상 탐색하지 않게 한다.

더 깊이 탐색하지 않아도 되는 경우는 길이가 N이상일 때, cnt가 K+1 이상일 때, isFinish가 true일 때, dp[a][b][c][cnt]가 true일 때이다.

만약 탐색을 마쳤는데 isFinish가 false라면 조건에 해당하는 답 S가 없는 경우이므로 -1을 출력한다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }

var N = 0
var K = 0
val dp = Array(31) { Array(31) { Array(31) { BooleanArray(450) } } }
var isFinish = false
lateinit var answer: CharArray
fun makeDP(a: Int, b: Int, c: Int, cnt: Int, len: Int) {
    if (cnt == K && len == N && !isFinish) {
        for(i in 0 until N){
            print("${answer[i]}")
        }
        isFinish = true
        return
    }
    if (len >= N) return
    if (cnt > K) return
    if (isFinish) return
    if (dp[a][b][c][cnt]) return
    dp[a][b][c][cnt] = true
    if (cnt + a <= K) {
        answer[len] = 'B'
        makeDP(a, b + 1, c, cnt + a, len+1)
    }
    if (cnt + a + b <= K) {
        answer[len] = 'C'
        makeDP(a, b, c + 1, cnt + a + b, len+1)
    }
    answer[len] = 'A'
    makeDP(a + 1, b, c, cnt, len+1)
}

fun main() {
    getIntList().also {
        N = it[0]
        K = it[1]
    }
    answer = CharArray(N)
    makeDP(0, 0, 0, 0, 0)
    if (!isFinish) println(-1)
}