[백준 1563] 개근상

1563번: 개근상

알고리즘 : DP

난이도 : 골드Ⅳ

 

1. 문제요약

• 개근상을 받으려면 지각을 두번이상 하면 안되고, 결석을 세번 연속으로 해서도 안된다.
• 한 학기가 N일(1000이하의 자연수)로 주어질 때, 개근상을 받을 수 있는 출결유형의 개수를 출력한다.
  예를 들어 한학기가 2일이고 출석을 O, 지각을 L, 결석을 A라고 표시할 때, 개근상을 받을 수 있는 출결유형은 모두 8개(OO, OL, OA, LO, LA, AO, AL, AA) 이므로 8을 출력하면 된다. 
• 다만 숫자가 너무 커지는 것을 방지하기 위해 정답은 1,000,000으로 나눈 나머지로 출력한다.

2. 아이디어

• 총 6가지 경우로 나누어, 길이 6인 dp배열 [A, B, C, D, E, F]을 생각하자.
  
  • case A : 지각 한번도 한적 없고, 마지막 날 결석하지 않은 경우
  • case B : 지각 한번도 한적 없고, 마지막 날(하루 연속) 결석한 경우
  • case C : 지각 한번도 한적 없고, 마지막 이틀 연속 결석한 경우
  • case D : 지각 한번 했고, 마지막 날 결석하지 않은 경우
  • case E : 지각 한번 했고, 마지막 날(하루 연속) 결석한 경우
  • case F : 지각 한번 했고, 마지막 이틀 연속 결석한 경우
• N-1일까지의 출결정보는 위 6가지 경우로 구별되고, 이를 통해 N일에서 가능한 출결정보를 구할 수 있다.
  • N-1일까지 출결정보 중 case A의 경우 N일차에는 출석, 지각, 결석 모두 가능하다.
  • case B의 경우에도 N일차에 출석, 지각, 결석 모두 가능하다.
  • case C의 경우 N일차에 출석, 지각 만 가능하다. N일차에 결석시 3일연속 결석이 되기 때문이다.
  • 마찬가지로 case D의 경우 출석과 결석, case E의 경우 출석과 결석, case F의 경우 출석만 가능하다.
• 위 관계로 부터 아래의 점화식을 도출할 수 있다.

$$A_N = A_{N-1} + B_{N-1} + C_{N-1}$$

$$B_N = A_{N-1}$$

$$C_N = B_{N-1}$$

$$D_N = A_{N-1} + B_{N-1} + C_{N-1} + D_{N-1} + E_{N-1} + F_{N-1}$$

$$E_N = D_{N-1}$$

$$F_N = E_{N-1}$$

3. 구현과정

• 위 점화식만 도출했다면 구현은 매우 간단하다. 초기 dp 배열이 [1,1,0,1,0,0] 이라는 점과, 임시 배열 tmp를 활용하여 dp배열을 계속 업데이트 한다는 점, 그리고 숫자가 너무 커지는 것을 방지하기 위해 1,000,000으로 나눈 나머지로 업데이트 한다는 점만 유의하면 된다.

4. 파이썬 코드

n = int(input())
dp = [1,1,0,1,0,0]
for _ in range(n - 1):
    tmp = [x % 10**6 for x in dp]
    dp[0] = tmp[0] + tmp[1] + tmp[2]
    dp[1] = tmp[0]
    dp[2] = tmp[1]
    dp[3] = tmp[0] + tmp[1] + tmp[2] + tmp[3] + tmp[4] + tmp[5]
    dp[4] = tmp[3]
    dp[5] = tmp[4]
print(sum(dp) % 10**6)