[C/C++] 백준 - 2876번 : 그래픽스 퀴즈

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

2876번: 그래픽스 퀴즈

문제

오늘은 기초컴퓨터그래픽스의 퀴즈가 있는 날이다. 기다란 교실 안에는 N개의 책상이 한 줄로 늘어서 있는데, 각 책상당 두 명의 학생이 앉도록 되어있다.

모든 학생들은 그래픽스를  열심히 공부했지만, 말도 안되는 난이도에 질려 포기하고 말았다. 한편 교수님은 각 학생들의 얼굴만 보고도 이 학생이 받아야 할 그레이드를 정확히 알아낼 수 있다.

교수님은 그래픽스 과목을 가르치는 만큼 자신의 미적 감각을 살리기 위해 각 그레이드를 다른 색을 이용해서 표시한다(예를 들어 A를 빨강으로 칠하면, B,C,D는 빨강으로 표시하지 않는다).

또, 퀴즈의 방식은 교수님이 수업이 시작할 때 어떤 두 책상을 선택하고, 두 책상과 그 사이에 있는 모든 책상에서 각각 한 명씩 지목해서 질문을 하고, 학생의 대답을 듣는 것이다.

오늘 교수님은 바쁜 나머지 한 가지 색의 색연필만 가지고 왔고, 결국 자신의 미학을 지키기 위해 퀴즈에서 지목한 모두에게 같은 그레이드를 주려고 한다. 교수님이 채점할 수 있는 학생의 수는 최대 몇 명일까?

 

 

 

채점을 최대한 많이 하기 위한 조건은

① 연속적으로 같은 그레이드를 가지는 학생들이 존재해야한다

② 시작 구간부터 모든 구간을 확인해주어야한다.

③ 이미 방문해서 확인했던 구간은 메모이제이션을 적용하여 값만 반환받는다.

 

동적계획법으로 위와 같이 구성하면 시간 내 통과가 가능하다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
int information[100003][2];
int cache[100003][8];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++){
		cin >> information[i][0] >> information[i][1];
	}
}

int path(int seat, int grade) {
	if (seat > N) return 0;
	if (information[seat][0] != grade && information[seat][1] != grade) return 0;
	int& ret = cache[seat][grade];
	if (ret != -1) return ret;
	ret = 1;
	return ret += path(seat + 1, grade);
}

void solution() {
	memset(cache, -1, sizeof(cache));
	int student = 0, answerGrade = INF;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 2; j++) {
			int temp = path(i, information[i][j]);
			if (student < temp) {
				student = temp;
				answerGrade = information[i][j];
			}
			else if (student == temp) answerGrade = min(answerGrade, information[i][j]);
		}
	}
	cout << student << " " << answerGrade << endl;
}

int main() {
	fastio;
	input();
	solution();
	 
	return 0;
}