☑️ 문제 분석

역의 개수 n, 롤러코스터 구간의 길이 m이 주어진다.

롤러코스터 구간이란, 지상/지하/지상/지하/... 와 같이 지상/지하가 반복되는 역 구간을 의미한다.

지상으로 설정된 역에는 5개의 승강장을 만들 수 있고,

지하로 설정된 역에는 11개의 승강장을 만들 수 있다.

즉, 연속된 두 역을 지상 - 지하로 설정하면 5 * 11 = 55가지가 가능한 것이다.

연속된 m 길이의 역 중 롤러코스터 구간이 몇가지가 가능한지 구하자.

✅ 문제 풀이

우선 역의 전체 개수인 n은 20이하이다.

각 역은 지상 혹은 지하로 설정되기 때문에 역마다 두가지 경우의 수가 존재한다.

만약 n이 20이라고 하면 2^20으로 대략 백만 개의 경우의 수가 가능한 것이다.

고로 완전 탐색을 사용해도 시간 제한 1초 내에 넉넉하게 통과 가능한 표본이다.

그래서 완전 탐색을 사용하는 것으로 풀이를 시작한다.

우선 입력을 받자. 완전 탐색에서 자주 참조할 변수들이기 때문에 전역 변수로 저장할 것이다.

private var n = 0
private var m = 0
private lateinit var S: List<String>
...

fun main() = with(System.`in`.bufferedReader()) {
    readLine().split(" ").map(String::toInt).run {
        n = first(); m = last()
    }
    S = List(n) { readLine() } // 얘는 사실 코드에서 사용될 일이 없는 변수임..
    ...
}

이제 완전 탐색 코드를 작성한다.

우리에게 필요한 건 특정 상황에서 롤러 코스터 구간의 길이가 m인지를 확인하는 것이다.

이 특정 상황이라 함은 2^20가지 경우의 수중 하나일 것이다.

그러니 2^20가지의 경우의 수를 모두 탐색해보자.

컴퓨터에게 모든 경우의 수를 탐색하게 하는 것은 재귀로 간단하게 구현할 수 있다.

한 역의 상태를 지상/지하로 설정하고 다음 역의 상태를 이어서 지상/지하로 설정하면 된다.

역의 상태는 List에 저장할 것이다. (어떤 자료구조에 저장하든 상관없음)

private val cands = mutableListOf<Int>()
...
private fun bruteforce(idx: Int) {
    ...
    cands.add(11) // 지하라는 의미로 지하역 승강장 가짓수를 추가한다.
    bruteforce(idx + 1) // 다음 역으로 이동
    cands.removeLast() // 재귀에서 돌아와서 가짓수 제거
    cands.add(5) // 지상이라는 의미로 지상역 승강장 가짓수를 추가한다.
    bruteforce(idx + 1) // 다음 역으로 이동
    cands.removeLast() // 재귀에서 돌아와서 가짓수 제거
}
...

이제 경우의 수를 만드는 코드는 완성되었고, 각 경우가 완성됐을 때 롤러코스터 구간이 m을 달성하는지 확인하면 된다.

만들어진 경우의 롤러코스터 구간이 m인지 확인하는 함수를 작성하자.

...
private fun check(): Boolean {
    var maxLength = 0
    var temp = 1 // 구간의 길이 일시적으로 기록
    
    for (i in 1 until n) {
        // 지상/지하 혹은 지하/지상의 경우
        if (cands[i - 1] != cands[i]) {
            temp++
        } else { // 지상/지상 혹은 지하/지하의 경우
            maxLength = maxOf(maxLength, temp)
            temp = 1
        }
    }
    
    return maxLength == m
}
...

이걸 bruteforce(idx: Int) 함수에 녹여내자.
경우의 수가 구성될 때마다, 롤러코스터 구간을 확인한 뒤, 그것이 m이라면 누적했던 수들을 곱해 가짓수를 계산한다.

private var answer = 0L
private const val MOD = 1e9.toInt() + 7
...
private fun bruteforce(idx: Int) {
    // 경우의 수가 완성됐을 때 롤러 코스터 구간 확인
    if (idx == n) {
        if (check()) {
            // 곱해줄 때도 MOD로 나눠주어야 한다. 
            // 최대 값인 11^20은 Long 범위마저 넘어선다.
            answer += cands.fold(1L) { acc, e -> (acc * e) % MOD }
            answer %= MOD
        }
        return
    }
    ...
}

이제 answer를 출력하기만 하면 정답.

...
fun main() = with(System.`in`.bufferedReader()) {
    ...
    bruteforce(0)
    print(answer)
}