[백준] 2876 : 그래픽스 퀴즈

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

2876번: 그래픽스 퀴즈

---

• 문제 이해하는게 더 어려운 문제이다.
• 요약해서 말하자면, 1 부터 N 까지 각각 두개의 값들이 들어오는데, i 번째의 두 값들 중 하나씩만을 선택할 경우 특정한 구간에서 가장 많이 연속되는 값을 찾는 것이다. (더 이해가 안될 수도..?)
• 즉 i 부터 j 번째 구간은 각각 두개의 값을 갖는데, 이들 중 하나씩만 선택한다고 했을 때 가장 많이 연속되는 값이다.
• 문제에서 주어진 예제를 보는 것이 도움이 많이 된다.
• 결국 i 번째 책상에서의 1~5등급 중 두 등급을 제외한 나머지 세 등급은 반드시 연결이 끊기게 된다.
• 두 등급의 경우에는 i-1 번째 책상에서의 연속값에 각각 1을 더해준(한번 더 연속되는) 값으로 생각할 수 있다.
• 이전에 연결이 끊겼던 등급이라고 할지라도 dp 배열이 0 으로 초기화 돼있으면 자연스럽게 1 로 증가된다.
• 스트리밍하게 처리하면서 최댓값을 갱신해주면 된다.

---

#include <iostream>

using namespace std;

int N, A, B;
int grades[100001][6];      // i 번째 책상까지 j 번째 등급의 최대 연속 값을 담는 dp 배열
int maxval, maxidx;

int main(void)
{
    cin >> N;
    for(int i = 1 ; i <= N ; i++)
    {
        cin >> A >> B;
        grades[i][A] = grades[i-1][A] + 1;      // 이전 책상까지의 값 + 1
        if(grades[i][A] > maxval)               // 최댓값 갱신
        {
            maxval = grades[i][A];
            maxidx = A;
        }
        if(A != B)                              // A 와 B 값이 같으면 하나만 처리해줘야 함
        {
            grades[i][B] = grades[i-1][B] + 1;  // 다를 경우에는 B 값에 대해서도 똑같은 처리
            if(grades[i][B] > maxval)
            {
                maxval = grades[i][B];
                maxidx = B;
            }
        }
    }
    cout << maxval << " " << maxidx << endl;
}