1309번: 동물원(Kotlin, C++)

제한사항

• 1 ≤ N ≤ 100,000
• 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

문제 정리

사자는 자신의 주위(사방면)에 다른 사자가 있으면 안된다.

사자를 둘 수 있는 방법을 모두 구하시오.

접근 방법

DP라고는 생각했는데 제한 시간 내에 못 풀어서 다른 사람 답안 봤습니다.

핵심은 위에 사자가 있는 경우와 위에 왼쪽에 사자가 있는 경우 위에 오른쪽에 사자가 있는 경우를 생각해서 풉니다.

 

case1) 현재 블록에 사자를 안 두는 경우

이 경우에는 위에 사자가 어디 있든 지 상관 없습니다. 따라서, 아래 세 가지 수의 합이 사자를 안 두는 경우입니다.

1. 위에 사자가 없는 경우(dp[n-1][0])
2. 위에 왼쪽에 사자가 있는 경우(dp[n-1][1])
3. 위에 오른쪽에 사자가 있는 경우(dp[n-1][2])

결과적으로 현재 n번째 블록에 사자를 안 두는 경우(dp[n][0])는 아래 공식이 나옵니다.

dp[n][0] = dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]

 

case2) 현재 블록에 왼쪽에 사자를 두는 경우

이 경우에는 위에 사자가 없거나, 위에 오른쪽에 사자가 있는 경우의 수의 합입니다.

1. 위에 사자가 없는 경우(dp[n - 1][0])
2. 위에 오른쪽에 사자가 있는 경우(dp[n - 1][2]

결과적으로 현재 n번째 블록에 사자를 왼쪽에 두는 경우(dp[n][1])는 아래 공식이 나옵니다.

dp[n][1] = dp[n - 1][0] + dp[n - 1][2]

 

case3) 현재 블록에 오른쪽에 사자를 두는 경우

이 경우에는 위에 사자가 없거나, 위에 왼쪽에 사자가 있는 경우의 수의 합입니다.

1. 위에 사자가 없는 경우(dp[n - 1][0])
2. 위에 왼쪽에 사자가 있는 경우(dp[n - 1][1])

결과적으로 현재 n번째 블록에 사자를 오른쪽에 두는 경우(dp[n][2])는 아래 공식이 나옵니다.

dp[n][2] = dp[n - 1][0] + dp[n - 1][1]

복잡도

• 시간복잡도 : O(n)
• 공간복잡도 : O(1)

코드

[Kotlin]

import java.io.BufferedReader
import java.io.InputStreamReader

const val modedNum = 9901

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var caseEmpty = 1
    var caseLeftExist = 1
    var caseRightExist = 1

    var currentCaseEmpty = 1
    var currentCaseLeftEmpty = 1
    var currentCaseRightEmpty = 1

    for (i in 2..n) {
        currentCaseEmpty = caseEmpty.plus(caseLeftExist).plus(caseRightExist).mod(modedNum)
        currentCaseLeftEmpty = caseEmpty.plus(caseRightExist).mod(modedNum)
        currentCaseRightEmpty = caseEmpty.plus(caseLeftExist).mod(modedNum)

        caseEmpty = currentCaseEmpty
        caseLeftExist = currentCaseLeftEmpty
        caseRightExist = currentCaseRightEmpty
    }
    println(currentCaseEmpty.plus(currentCaseLeftEmpty).plus(currentCaseRightEmpty).mod(modedNum))
}

[C++]

#include "iostream"

using namespace std;

const int modNum = 9901;
int n;

int main() {
    cin >> n;
    int caseEmpty = 1;
    int caseLeftExist = 1;
    int caseRightExist = 1;

    int currentCaseEmpty = 1;
    int currentCaseLeftEmpty = 1;
    int currentCaseRightEmpty = 1;

    for (int i = 2; i <= n; i++) {
        currentCaseEmpty = (caseEmpty + caseLeftExist + caseRightExist) % modNum;
        currentCaseLeftEmpty = (caseEmpty + caseRightExist) % modNum;
        currentCaseRightEmpty = (caseEmpty + caseLeftExist) % modNum;

        caseEmpty = currentCaseEmpty;
        caseLeftExist = currentCaseLeftEmpty;
        caseRightExist = currentCaseRightEmpty;
    }

    cout << (currentCaseEmpty + currentCaseLeftEmpty + currentCaseRightEmpty) % modNum << endl;
    return 0;
}