[백준/BOJ] 1536 개근상 - 접근과 풀이 (c++)

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

1563번: 개근상

웹 공부를 하기 싫을때 나는 백준을 푼다. dp를 풀면 마음이 평온해지기 때문이다.

---

접근 방법

 

개근상을 받지 못하는 조건이 명확히 나온다. 두번 이상의 지각 또는 연속된 세번의 결석. 

N+1일에서 출석, 지각, 결석 세 가지의 경우가 가능하고, 이는 N일의 상태에서 가져오는 전형적인 바텀-업 dp문제.

dp[N][late][consAbs];  N일까지 총 지각한 횟수와, N일까지 연속된 결석의 횟수를 기록해야한다.

late는 0,1만 가능하고 consAbs는 0,1,2 만 가능하다.

 

1. N+1일에 출석하는 경우
   지각한 횟수는 초기화되지 않고, 결석한 횟수는 초기화된다.
2. N+1일에 지각하는 경우
   지각한 횟수를 늘리고, 결석한 횟수는 초기화된다.
3. N+1일에 결석하는 경우
   지각한 횟수는 초기화 되지않고, 결석한 횟수는 늘어난다.
   
   

---

풀이

 

tag : dp

#include<iostream>
#define MOD 1000000
using namespace std;
int dp[1001][2][3]={0}; //day, late, consAbs
int N;
void solve(){
  dp[1][0][0]=1;
  dp[1][1][0]=1;
  dp[1][0][1]=1;

  for(int i=2;i<=N;i++){
    //출석
    for(int j=0;j<3;j++){
      dp[i][0][0]+=dp[i-1][0][j];
      dp[i][1][0]+=dp[i-1][1][j];
      // 지각
      dp[i][1][0]+=dp[i-1][0][j];

      dp[i][0][0]%=MOD;
      dp[i][1][0]%=MOD;
    }
    //결석
    for(int j=1;j<3;j++){
      dp[i][0][j]+=dp[i-1][0][j-1];
      dp[i][1][j]+=dp[i-1][1][j-1];

      dp[i][0][j]%=MOD;
      dp[i][1][j]%=MOD;
    }
  }
}
int main(){
  cin>>N;
  solve();
  cout<<(dp[N][0][0]+dp[N][0][1]+dp[N][0][2]+
        dp[N][1][0]+dp[N][1][1]+dp[N][1][2])%MOD;
}

골드 4는 아니고 실1 ~골5 정도인듯