[백준] 1563번 개근상

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> 이유는 브루트포스로 문제 풀이를 생각해보면 시간 초과가 나기 때문에 메모이제이션을 이용해서 풀이해보도록 한다.

 

N이 1000이고 지각 2번, 결석 3번에 대한 모든 조합을 생각해보면 서로 다른 알파벳 3개 중에

​

1번은 1000개 중복, 2번은 2개 중복, 3번은 3개 중복이므로 #중복조합 은

 

n.H.r={n+r-1).C.r -> 이가 된다. ( '.' 콤마는 순열, 조합 기호 표시를 가시적으로 잘 보여주기 위해 임의로 삽입 )

 

서로 다른 (n + r - 1)개의 수 중, r개를 뽑는 경우의 수 )로 1002.C.2 가 되고 1000000 연산이 필요한데 n이 1 ~ 1000 에 따른 모든 수를 구하기 위해서는 시간 초과가 나게 됩니다.

 

(2) DP 배열 정의

 

-> 2. DP[n][i][j] : n일까지 i번 지각, j번 결석한 경우에 개근상을 받을 수 있는 총 개수

 

(3) 풀이 방법

 

-> 총 2번 지각, 3번 연속 결석의 제약조건만 잘 처리해주면 풀 수 있는 문제입니다.

 

    *** 지각의 경우는 2번인 경우 개근상을 주지 않으면 되지만, 결석인 경우는 연속적으로 결석을 하다가 한 번 지각 or           정상 출석을 하면 0으로 초기화 해주면서 풀 수 있습니다.

 

2. Source Code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 1001
#define MOD 1000000
using namespace std;
//https://www.acmicpc.net/problem/1563
int n;
// dp[n][i][j] , n일 중에 i번 지각, "연속" j 번 결석을 한 경우
// 배열은 전부 가독성 좋게 인덱스 1부터 시작하기로 했다.
long long dp[MAX][3][4];
/*
	O : 출석, L : 지각, A : 결석

	개근상 못 받는 조건

	-> 지각을 두 번 이상 or 결석 세 번 연속으로 한 사람

	1 학기는 N일이다.
	-> N이 주어졌을 때 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하라

	접근 방식

	1. 출석, 지각 , 결석을 각 각 보기 편하게 0 , 1 , 2 의 숫자로 바꾼다.

	2. N중에 1이 총 두 번 or 2가 연속 3번 있는 경우 개근 상을 못 받는다.
*/

long long solution(int day, int late, int absent)
{
	if (day == n)
	{
		if (late == 2 || absent == 3)
			return 0;
		else
			// 개근상 받는 경우
			return 1;
	}
	// 개근상 못 받는 경우
	if (late == 2 || absent == 3) return 0;

	long long& result = dp[day][late][absent];
	if (result != -1)
		return result;

	result = 0;
	// 결석을 한 경우
	//result += solution(day + 1, late, absent + 1);
	// 결석은 연속적이어야하므로 결석하지 않은 날 (지각 or 정상 출석)
	// 은 결석을 0으로 초기화해준다.
	// 지각을 한 경우
	//result += solution(day + 1, late + 1, 0);
	// 지각, 결석 둘다 안한 경우
	//result += solution(day + 1, late, 0);
	
	return result += (solution(day + 1, late, absent + 1) + solution(day + 1, late + 1, 0)
		+ solution(day + 1, late, 0)) % MOD;
}

int main()
{
	cin >> n;
	memset(dp, -1, sizeof(dp));
    // 첫날 정상 출석한 경우, 지각한 경우, 결석한 경우를 전부 더해준다.
	cout << (solution(1, 0, 0) + solution(1, 0, 1) + solution(1, 1, 0)) % MOD;
	return 0;
}

3. 비슷한 문제

1. 다이나믹 프로그래밍 관련 문제

4. 참조

---

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