백준 14238 출근 기록 Kotlin (dp)

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

14238번: 출근 기록

문제

스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다.

이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다.

A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다. 

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 출근 기록 S가 주어진다. S의 길이는 50을 넘지 않는다.

출력

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 없는 경우에는 -1을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

풀이

재귀 dp 문제이다.

정답은 최대 길이가 50인 문자열이고 각 칸에 오는 알파벳은 A,B,C인데 B와 C는 조건부다.

B는 이전 칸에 B가 있는 경우 올 수 없고

C는 이전 칸, 혹은 전전 칸에 C가 있는 경우 올 수 없다.

이를 감안하더라도 경우의 수는 굉장히 많기 때문에 적절한 가지치기를 해주어야 하고 이에 dp를 이용할 수 있다.

dp[a][b][c][prev][pprev]는 A가 a개 남고, B가 b개 남고, C가 c개 남고, 이전 칸이 prev(A,B,C), 전전 칸에 pprev(A,B,C)

인 상태를 이미 체크했는지 판단한다.

만약 dp[1][2][1][1][2] = true 라면, A는 1개 남고, B는 2개 남고, C는 1개 남고 이전 칸이 A, 전전 칸이 B인 경우를 이미 확인했다는 의미이다.

여기서 몇 개 남았다는 것은 입력으로 주어진 문자열에서 A,B,C가 나온 횟수를 카운트하여 알 수 있고, 알파벳을 사용함에 따라 해당 알파벳의 카운트를 하나씩 줄여주는 것으로 구현할 수 있다.

또 알파벳은 숫자로 치환해주었는데, A는 1, B는 2, C는 3으로 치환해서 prev의 초기값을 0으로 두었다.

 

이제 재귀 함수에 정답 문자열을 저장할 ans를 매개 변수로 두고 정답 조건인 ans의 길이가 50이하일 때 a==0 && b==0 && c==0, 즉 입력으로 주어진 문자들을 모두 사용한 경우를 찾는다.

이때 dp배열을 이용해 이미 체크한 상태는 건너뜀으로 재귀함수 호출 횟수를 훨씬 줄여, 각 상태마다 한 번씩만 방문하게 할 수 있다. 

 

코드

val br = System.`in`.bufferedReader()

val dp = Array(50) { Array(50) { Array(50){Array(4){BooleanArray(4) } } } }
var isFinish = false
fun makeDP(a: Int, b: Int, c: Int, prev: Int, pprev: Int, ans: StringBuilder) {
    if(ans.length>50) return
    if (a == 0 && b == 0 && c == 0) {
        println(ans)
        isFinish = true
        return
    }
    if(isFinish) return
    if(dp[a][b][c][prev][pprev]) return
    dp[a][b][c][prev][pprev] = true
    if (a > 0) {
        ans.append('A')
        makeDP(a - 1, b, c, 1, prev,ans)
        ans.deleteCharAt(ans.lastIndex)
    }
    if (b > 0 && prev != 2) {
        ans.append('B')
        makeDP(a, b-1, c, 2, prev,ans)
        ans.deleteCharAt(ans.lastIndex)
    }
    if (c > 0 && prev != 3 && pprev != 3) {
        ans.append('C')
        makeDP(a, b, c - 1, 3, prev,ans)
        ans.deleteCharAt(ans.lastIndex)
    }
}

fun main(){
    val input = br.readLine()
    val cnt = IntArray(4)
    for (ch in input) {
        when (ch) {
            'A' -> cnt[1]++
            'B' -> cnt[2]++
            else -> cnt[3]++
        }
    }
    makeDP(cnt[1], cnt[2], cnt[3], 0, 0,StringBuilder())
    if (!isFinish) {
        println(-1)
    }
}