[파이썬] 백준 1563 : 개근상 (골드4)

[파이썬] 백준 1563 : 개근상 (골드4)

 

1563번: 개근상

---

문제

---

풀이

0. 방향성 생각

상태도 DP로 접근

상태도 분류

누적지각0~1회,연속결석0~2회,개근상불가 -> 총 7가지 경우

1. 입력

n = int(input())

dp = [[0]*7 for _ in range(n)]
dp[0] = [1,1,0,1,0,0,0]

k = 1000000
filters =  [[1,1,1,0,0,0,0],
            [1,0,0,0,0,0,0],
            [0,1,0,0,0,0,0],
            [1,1,1,1,1,1,0],
            [0,0,0,1,0,0,0],
            [0,0,0,0,1,0,0],
            [0,0,1,1,1,2,0]]

1번 상태 : 누적지각 0회, 연속결석 0회

2번 상태 : 누적지각 0회, 연속결석 1회 

3번 상태 : 누적지각 0회, 연속결석 2회 

4번 상태 : 누적지각 1회, 연속결석 0회 

5번 상태 : 누적지각 1회, 연속결석 1회 

6번 상태 : 누적지각 1회, 연속결석 2회 

7번 상태 : 개근상 불가능

 

처음에 출석, 결석, 지각 순서대로 1 2 4 번 상태이므로 시작노드 활성화 시켜준다.

이후 다음상태가 주어질 때 이전상태에서 다음상태로 천이가 가능한 노드만 활성화 시켜준다.

filters[다음상태] = 이전상태 합

 

ex) 개근상 못받는 경우 : filters[6] : 7번 상태

누적지각 1인 상태에서 지각 한 번 더하거나 결석2회에서 결석 한 번 더하면 된다.

연속결석 2회인 3,6번노드를 켜주고, 누적지각 1회인 4,5,6번 노드를 켜준다.
누적지각1, 연속결석2인 상태에서는 지각 결석 2가지 경우 모두 처리해야하므로 2

2. 출력

for day in range(n-1):
    for state in range(7):
        dp[day+1][state] += sum(map(lambda x,y:x*y,dp[day],filters[state]))
        dp[day+1][state] %= k

print(sum(map(lambda x,y:x*y,dp[-1],[1,1,1,1,1,1,0]))%k)

불가능한 경우 빼고 카운트

---

전체코드

n = int(input())

dp = [[0]*7 for _ in range(n)]
dp[0] = [1,1,0,1,0,0,0]

k = 1000000
filters =  [[1,1,1,0,0,0,0],
            [1,0,0,0,0,0,0],
            [0,1,0,0,0,0,0],
            [1,1,1,1,1,1,0],
            [0,0,0,1,0,0,0],
            [0,0,0,0,1,0,0],
            [0,0,1,1,1,2,0]]

for day in range(n-1):
    for state in range(7):
        dp[day+1][state] += sum(map(lambda x,y:x*y,dp[day],filters[state]))
        dp[day+1][state] %= k

print(sum(map(lambda x,y:x*y,dp[-1],[1,1,1,1,1,1,0]))%k)

 

다른풀이

n = int(input())

# 출석 / 지각 / 결석
# 개근상 x : 지각 2번 이상 or 결석 3연속
# dp1 : dp1[지각횟수 0 1][현재날짜][연속결석]

dp = [[[0]*3 for _ in range(n)] for _ in range(2)]
dp[0][0][:2] = [1,1]
dp[1][0][0] = 1
k = 10**6

for day in range(n-1):
    
    # 지0 : 출석하는경우 결0 결1 결2에서
    dp[0][day+1][0] += sum(dp[0][day])%k
    
    # 지1 : 출석하는경우 결0 결1 결2에서
    dp[1][day+1][0] += (sum(dp[0][day])+sum(dp[1][day]))%k
    
    # 지각 0회 상태 : 결석하는경우
    dp[0][day+1][1] += dp[0][day][0]%k 
    dp[0][day+1][2] += dp[0][day][1]%k
    
    # 지각 1회 상태 : 결석하는 경우
    dp[1][day+1][1] += dp[1][day][0]%k
    dp[1][day+1][2] += dp[1][day][1]%k

print((sum(dp[0][-1])+sum(dp[1][-1]))%k)

dp[누적 지각 횟수 : 0~1][현재 날짜 : 0~n-1][연속 결석 횟수]