boj, 백준) 1563. 개근상 ( C / C++)

1. 문제 링크

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

1563번: 개근상

 

2. 문제 개요

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

 개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

 

3. 문제 힌트

 dp배열을 어떻게 정의하느냐에 따라서 문제를 바로 풀고 못풀고가 나뉜다.

우선, 날짜정보는 들어가야 하고, 추가적으로 지각한 횟수, 연속으로 결석한 횟수를 기록하자.

따라서 dp[날짜][지각][연속으로 결석한 횟수]로 정의하자.

이 배열이 갖는의미는 개근상을 받을 수 있는 사람 수이다.

 

 

4. 문제 풀이

 

풀이는 Bottom up 방식으로 한다.

 

결국 n번째 어떤 날에서 개근상을 받을 수 있는 사람들의 조건은 다음과 같다

(1) 0번 지각 0번 연속 결석

(2) 0번 지각 1번 연속 결석

(3) 0번 지각 2번 연속 결석

(4) 1번 지각 0번 연속 결석

(5) 1번 지각 1번 연속 결석

(6) 1번 지각 2번 연속 결석 이 되겠다.

 

그럼 n번째 날에 대해서 n-1번째 날의 정보를 어떻게 사용할지 보자.

n번째 날의 0번 지각 0번 연속 결석은 n-1번째 날에서 어떤 사람에게서 올까?

0 연속 결석이니까 결석은 x, 0번 지각이니까 지각도 x, 무조건 출석을 해야만 도달할 수 있다. 따라서,

dp[날짜][지각][연속 결석]으로 뒀을때,

dp[n][0][0] = dp[n-1][0][0] + dp[n-1][0][1] + dp[n-1][0][2]

가 될 수 있다. 1번, 2번 연속 결석한 사람도 출석을 하면 0번으로 초기화된다는 것을 유념하자.

 

그럼 dp[n][0][1]은 어떨까

1번 연속 결석이니까 무조건 결석을 해야 한다.

따라서

dp[n][0][1] = dp[n-1][0][0]

밖에 안된다.

dp[n][0][2]도 마찬가지다

dp[n][0][2] = dp[n-1][0][1]

이 되어야 한다.

 

dp[n][1][0]은 어떨까?

지각해서 도달할 수도 있고, 출석해서 도달할 수도 있다.

여러 번 연속으로 결석했지만 지각하면 결석 스택이 초기화되는 걸 주의하자.

dp[n][1][0] = dp[n - 1][0][0] + dp[n - 1][0][1] + dp[n - 1][0][2] + dp[n - 1][1][0] + dp[n - 1][1][1] + dp[n - 1][1][2]

dp[n][1][1], dp[n][1][2]는 dp[n][0][1], dp[n][0][2]와 비슷한 구조다.

 

 

 

5. 코드

bottom-up

#include <cstdio>
using namespace std;

const int divval = 1000000;
int dp[1001][2][3];
//day, late, abs
int main()
{
	int n;
	scanf("%d", &n);

	dp[1][0][0] = dp[1][1][0] = dp[1][0][1] = 1;

	for (int i = 2; i <= n; ++i) {
		dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2])% divval;	
		dp[i][0][1] = (dp[i - 1][0][0])% divval;
		dp[i][0][2] = (dp[i - 1][0][1])% divval;
		dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % divval;
		dp[i][1][1] = (dp[i - 1][1][0]) % divval;
		dp[i][1][2] = (dp[i - 1][1][1]) % divval;
	}
	
	int ans = (dp[n][0][0] + dp[n][0][1] + dp[n][0][2] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]) % divval;

	printf("%d", ans);
	return 0;
}

 

 

 

top-down

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int divval = 1000000;
int dp_table[1001][2][3];
//day, late, abs
int n;

int dp(int day, int late, int absent)
{
	if (late == 2)	return 0;
	if (absent == 3)	return 0;
	if (day > n)	return 1;

	int &cache = dp_table[day][late][absent];
	if (cache != -1)	return cache;


	//출석한경우, 지각한경우, 결석한경우
	cache = (dp(day + 1, late, 0) + dp(day + 1, late + 1, 0) + dp(day + 1, late, absent + 1))%divval;

	return cache;
}

int main()
{
	scanf("%d", &n);

	memset(dp_table, -1, sizeof(dp_table));

	printf("%d", dp(1,0,0));
	return 0;
}

 

지적, 댓글 언제나 환영입니다~