[BOJ] Q1309 사자 넣기

[BOJ] Q1309 사자 넣기

Question

Language: Python

Difficulty: Silver 1

해당 문제의 경우의 수를 분석해보면 3,7,17,41 … 의 형태인데 이를 분석해보면 F_n=2*F_n-1+F_n-2 형태의 점화식을 얻을 수 있다.

하지만, DP 방식으로 문제를 접근해보면 아래와 같이 풀이를 할 수 있다.

0=사자가 없는 경우, 1=사자가 왼쪽에 있는 경우, 2= 사자가 오른쪽에 있는 경우

1. 해당 행에 사자를 넣지 않는 경우 사자가 어디있는 상관이 없다 따라서, dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]

2. 왼쪽 칸에 사자를 넣는 경우 이전 행에 사자가 오른쪽에 있으면 안된다. dp[i][1]=dp[i-1][0]+dp[i-1][2]

3. 오른쪽 칸에 사자를 넣는 경우 dp[i][2]=dp[i-1][0]+dp[i-1][1]

와 같은 형태로 생각을 해볼 수 있다. 이후, 해당 행에 대한 합으로 사자를 넣는 경우의 수를 계산할 수 있다.

Solution 1

def solution():
    sub_sum=2
    dp=[0] * (num+1)
    dp[0]=1
    dp[1]=3
    if num>=2:
        for i in range(2,num+1):
            dp[num]=(2*dp[num-1] + dp[num-2]) % 9901

    return dp[num]

if __name__ == "__main__":
    num=int(input())
    print(solution())

Solution 2

def solution():
    sub_sum=2
    dp=[[0] * 3 for _ in range(num+1)]
    dp[1]=[1,1,1]

    if num>=2:
        for i in range(2,num+1):
            dp[num][0]=(dp[num-1][0]+dp[num-1][1]+dp[num-1][2]) % 9901
            dp[num][1]=(dp[num-1][0]+dp[num-1][2]) % 9901
            dp[num][2]=(dp[num-1][0]+dp[num-1][1]) % 9901

    return sum(dp[num])

if __name__ == "__main__":
    num=int(input())
    print(solution())

Solution 3

def solution():
    left,right,zero=1,1,1
    row_sum=sum(left,right,zero)

    if num>=2:
        for i in range(2,num+1):
            left,right,zero=row_sum-right,row_sum-left,row_sum
            row_sum=sum(left,right,zero) % 9901

    return row_sum

if __name__ == "__main__":
    num=int(input())
    print(solution())