아이디어

• 부분 최적문제이므로 dp로 풀어보자.
  • memo[날짜][지각횟수][결석횟수]와 같이 3차원 동적 테이블을 정의하자.
  • 각 날짜를 1일자부터 돌며 현재 날짜가 출석, 결석, 지각일 경우를 처리한다.
    • 출석일 때: 지각 횟수는 그대로, 결석 횟수는 0이 된다.
    • 결석일 때: 지각 횟수는 그대로, 결석 횟수는 1 증가한다.
    • 지각일 때: 지각 횟수는 1 증가, 결석 횟수는 0이 된다.
    • 최초 1일차에 출석일 경우, 지각일 경우, 결석일 경우에 1 씩 할당하고 시작한다.
    • 덧셈 대신 모듈로 덧셈을 사용해야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;
	
	static final int MOD = 1000000;
	
	static int N, ans;
	static int[][][] memo;	// [day][late][absent]

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		memo = new int[N+1][2][3];
		
		memo[1][0][0] = 1;
		memo[1][1][0] = 1;
		memo[1][0][1] = 1;
		
		for (int i=2; i<=N; i++) {
			// O
			for (int l=0; l<2; l++) for (int a=0; a<3; a++)
				memo[i][l][0] = add(memo[i][l][0], memo[i-1][l][a]);
			// A
			for (int l=0; l<2; l++) for (int a=1; a<3; a++)
				memo[i][l][a] = add(memo[i][l][a], memo[i-1][l][a-1]);
			// L
			for (int l=1; l<2; l++) for (int a=0; a<3; a++)
				memo[i][l][0] = add(memo[i][l][0], memo[i-1][l-1][a]);
		}

		for (int l=0; l<2; l++) for (int a=0; a<3; a++)
			ans = add(ans, memo[N][l][a]);
		
		System.out.println(ans);
	}
	
	static int add(int a, int b) {
		return (a + b) % MOD;
	}
}

메모리 및 시간

• 메모리: 14292 KB
• 시간: 128 ms

리뷰

• 처음에 DP임을 떠올리기 어려웠던 문제, 경우의 수를 나눠 풀어야 하는 수학 문제인 줄 알았다.
  • (전체 경우의 수) - (지각 2번 이상 횟수) - (결석 3연속 이상 횟수) + (지각이면서 결석 수)
  • 마지막 (지각 2번 이상이면서 결석 3연속인 횟수)를 구하기 어려워서 아니라고 생각했다.