2876번. 그래픽스 퀴즈

 

아이디어

dp[i][0] 을 i 번째 책상의 왼쪽에 앉은 학생을 선택했을 때 채점할 수 있는 최대 학생 수

dp[i][1] 을 i 번째 책상의 오른쪽에 앉은 학생을 선택했을 때 채점할 수 있는 최대 학생 수 라고 하면

 

해당 학생의 그레이드가 i - 1 번째 책상에 앉은 학생들의 그레이드와 같다면

 

dp[i][j] = dp[i][0] + 1 or dp[i][1] + 1

 

이 될 것이고 같은 그레이드가 없다면

 

dp[i][j] = 1

 

이 된다.

 

따라서 이를 고려해서 프로그램을 구현하면 원하는 답을 얻을 수 있다.

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[][] grades = new int[N][2];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                grades[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[N][2];
        dp[0][0] = dp[0][1] = 1;

        int cnt = dp[0][0];
        int grade = Math.min(grades[0][0], grades[0][1]);

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 2; j++) {
                dp[i][j] = 1;

                if (grades[i][j] == grades[i - 1][0]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][0] + 1);
                }

                if (grades[i][j] == grades[i - 1][1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][1] + 1);
                }

                if (cnt < dp[i][j]) {
                    cnt = dp[i][j];
                    grade = grades[i][j];
                } else if (cnt == dp[i][j]) {
                    grade = Math.min(grade, grades[i][j]);
                }
            }
        }

        System.out.println(cnt + " " + grade);
    }
}