[백준] Ezreal 여눈부터 가네 ㅈㅈ(Kotlin)

문제

https://www.acmicpc.net/problem/20500

---

풀이(10분)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private const val MOD = 1_000_000_007
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st: StringTokenizer

    st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    val arr = Array(N + 1) { Array(3) { 0 } } // 3으로 나누었을 때 나머지가 0 1 2
    arr[1][1] = 1 // 1일 때는 3으로 나눈 경우 나머지가 1
    arr[1][2] = 1 // 5일 때는 3으로 나눈 경우 나머지가 1

    for (i in 2..N) {
        arr[i][0] = (arr[i - 1][2] + arr[i - 1][1]) % MOD// 이전에 나머지가 2인 경우 1과 합치면 0, 1인 경우 5와 합치면 0
        arr[i][1] = (arr[i - 1][0] + arr[i - 1][2]) % MOD // 이전에 나머지가 0인 경우 1과 합치면 1, 2인 경우 5와 합치면 1
        arr[i][2] = (arr[i - 1][0] + arr[i - 1][1]) % MOD // 이전에 나머지가 0인 경우 5와 합치면 2, 1인 경우 1과 합치면 2
    }

    println(arr[N - 1][1])
}

---

문제 풀이 전략

 

💡 문제 접근

이 문제는 1과 5로만 이루어진 수 중 15의 배수가 되는 경우의 수를 구하는 문제다.
먼저, 15의 배수 판별법부터 생각해볼 필요가 있다.

---

🔹15의 배수 판별법

15를 소인수분해하면

15=3×515 = 3 \times 515=3×5

따라서 15의 배수는 3의 배수이면서 동시에 5의 배수여야 한다.

---

🔹 5의 배수 판별

5의 배수는 끝자리가 0 또는 5인 수다.
하지만 이 문제에서는 사용할 수 있는 숫자가 1과 5뿐이다.
따라서 끝자리가 0인 경우는 존재하지 않으며,
15의 배수가 되기 위해서는 반드시 끝자리가 5여야 한다.

---

🔹 3의 배수 판별

3의 배수는 각 자리 숫자의 합이 3의 배수인 수다.
즉, 1과 5로 이루어진 수라면 각 자리의 합을 3으로 나눈 나머지를 추적하면 된다.
이 아이디어를 이용해 DP를 설계할 수 있다.

---

💡 DP 접근 아이디어

arr[i][r]을 i자리 수 중에서 자리합을 3으로 나눈 나머지가 r인 경우의 수로 정의한다.
(r은 0, 1, 2 중 하나다)

• arr[i][0] → 자리합이 3으로 나누어떨어지는 경우의 수
• arr[i][1] → 자리합을 3으로 나눈 나머지가 1인 경우의 수
• arr[i][2] → 자리합을 3으로 나눈 나머지가 2인 경우의 수

이전 자리 상태(i - 1)에서 1 또는 5를 붙였을 때
자리합의 나머지가 어떻게 변하는지를 이용해 점화식을 세운다.

---

✅ 결론

끝자리는 항상 5여야 하므로,
마지막 자리(N번째 자리)는 5로 고정된다.
따라서 마지막 자리 바로 전(N - 1번째 자리)까지의 자리합을
3으로 나눈 나머지가 1이어야 한다.
즉, 정답은 arr[N - 1][1]이 된다.