[BOJ 1563] 개근상 C++ 풀이

문제 링크

www.acmicpc.net/problem/1563

1563번: 개근상

개근상 성공분류

시간 제한 2 초

메모리 제한 128 MB

제출 2697

정답 1268

맞은 사람 1020

비율 50.570%

문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

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

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA LAOO LAOA LAAO

총 43가지이다.

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

입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

풀이

접근이 난해한 DP문제였지만, 접근에 따라 매우 쉽게 느껴질 수도 있는 문제였습니다.

지각을 2번 이상 또는 결석을 3번 '연속'으로 한 경우 개근상을 받을 수 없다.는 조건을 잘 이용해야 합니다.

 

저는 우선 DP배열을 아래와 같이 선언하였습니다

dp[지각수][연속결석수][출결일수] = 가능한 개수

최대 지각 수 1, 최대 연속 결석일 수 2를 넘어가게 되면, 개근상을 받을 수 없으므로 셀 필요가 없습니다.

따라서, dp 배열은 dp[2][3][1001]으로 선언하였습니다.

 

dp 배열은 지각0~1, 연속 결석일0~2, 출결일 수로,

i번째 날에는 i번째 전 날 까지,

 

dp[0][0][i] = 모두 출석 + 연속결석 1회 + 연속결석 2회

dp[0][1][i] = 모두 출석

dp[0][2][i] = 연속 결석 1회

dp[1][0][i] = 모두 출석 + 연속 결석 1회 + 연속 결석 2회 + 지각 1회 + (지각1회, 연속 결석1회) + (지각1회, 연속 결석2회)

dp[1][1][i] = 지각1회

dp[1][2][i] = (지각 1회, 연속결석 1회)

※ 연속 결석은 다음날 지각 or 출석시 0회로 초기화 된다는 것을 주의!

 

의 수를 연산 한 후,

dp[0~1][0~2][출결일수] 를 출력하면 되는 문제였습니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MOD 1000000

int N;
int dp[2][3][1001];
// dp[지각일][연속결석일][출결일수N]
int ans = 0;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> N;
    
	dp[0][0][1] = 1;
	dp[1][0][1] = 1;
	dp[0][1][1] = 1;

	for (int i = 2; i <= N; i++)
	{
		// 본문에서 설명한 경우 연산
		dp[0][0][i] = dp[0][0][i - 1] + dp[0][1][i - 1] + dp[0][2][i - 1];
		dp[0][1][i] = dp[0][0][i - 1];
		dp[0][2][i] = dp[0][1][i - 1];
		dp[1][0][i] = dp[0][0][i - 1] + dp[0][1][i - 1] + dp[0][2][i - 1] + dp[1][0][i - 1] + dp[1][1][i - 1] + dp[1][2][i - 1];
		dp[1][1][i] = dp[1][0][i - 1];
		dp[1][2][i] = dp[1][1][i - 1];

		for (int j = 0; j < 2; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				//각 연산에 대해서 100만으로 나머지 연산
				dp[j][k][i] %= MOD;
			}
		}
	}
    
	for (int j = 0; j < 2; j++)
	{
		for (int k = 0; k < 3; k++)
		{
			//ans에 N번째 날의 지각0~1, 연속 결석0~2 을 모두 더해줌
			ans+=dp[j][k][N];
		}
	}
    
	// dp[j][k][N]는 999,999까지 나올 수 있으므로, 더하면 100만을 쉽게 넘어감
	// 따라서 100만으로 나머지 연산을 추가로 해줌
	ans %= MOD;
	cout << ans << '\n';
}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.