[Python] 백준 1563번: 개근상

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

1563번: 개근상

 

우선 중요한 요소들이 몇 개 있다.

1. L이 1번이라도 들어갔는가

2. 맨 뒤에 A가 1번 붙었는가

3. 맨 뒤에 A가 2번 연속으로 붙었는가

 

이것을 통해 '상태'를 총 6개를 만들 수 있다. 상태의 네이밍과 설명은 다음과 같다.

 - O: 기본

 - A: 맨 뒤에 A 1개

 - AA: 맨 뒤에 A 2개

 - L: L이 1개 있고, 맨 뒤에 A 없음

 - LA: L이 1개 있고, 맨 뒤에 A 1개

 - LAA: L이 1개 있고, 맨 뒤에 A 2개

 

이것을 통해 state diagram을 그릴 수 있다.

진행은 맨 뒤에 문자를 하나 붙이는 식이다. 예를 들어, AA 상태인 "OAA"에 L을 붙여서 "OAAL", 즉 LO 상태가 된다.

길이가 M일 때의 각 상태에서의 카운트를 통해 M+1에서의 카운트를 얻을 수 있다. 코드는 아래와 같이 짤 수 있다.

import sys
input = sys.stdin.readline
O, A, AA, LO, LA, LAA = 0, 1, 2, 3, 4, 5

if __name__ == '__main__':
    N = int(input())

    dp = [[0, 0, 0, 0, 0, 0] for _ in range(N+1)]
    dp[1] = [1, 1, 0, 1, 0, 0]

    for i in range(2, N+1):
        o, a, aa, lo, la, laa = dp[i-1]

        dp[i][O] += o + a + aa
        dp[i][LO] += o + a + aa + lo + la + laa
        dp[i][A] += o
        dp[i][AA] += a
        dp[i][LA] += lo
        dp[i][LAA] += la

    print(sum(dp[N]) % 1000000)

 

이것을 아래와 같이 최적화 시킬 수 있다.

 

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())

    prev = [1, 1, 0, 1, 0, 0]
    for i in range(2, N+1):
        o, a, aa, lo, la, laa = prev
        prev = [o + a + aa, o, a, sum(prev), lo, la]

    print(sum(prev) % 1000000)

 

dp가 가장 최근의 것만 필요하기 때문에 위처럼 할 수 있다.

사실 prev라는 리스트는 필요하지 않아서 아래처럼 할 수도 있다.

 

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())

    o, a, aa, lo, la, laa = 1, 1, 0, 1, 0, 0
    for i in range(N-1):
        o, a, aa, lo, la, laa = o + a + aa, o, a, o + a + aa + lo + la + laa, lo, la

    print((o + a + aa + lo + la + laa) % 1000000)