[Python/파이썬] 백준 2876번 그래픽스 퀴즈

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

 

코드

import sys
input = sys.stdin.readline

n = int(input())
grades = [(0, 0)]
for _ in range(n):
    a, b = map(int, input().split())
    grades.append((a, b))

dp = [[[0]*2 for _ in range(2)] for _ in range(n+1)]    # 왼쪽 학생, 오른쪽 학생
ans = [0, 5]    # 명수, 그레이드

for i in range(1, n+1):
    for j in range(2):  # i번째 책상의 2명의 학생
        dp[i][j][1] = grades[i][j]   # 그레이드
        for k in range(2):  # i-1번째 책상까지의 누적값 2개
            if grades[i][j] == dp[i-1][k][1]:    # 같은 그레이드를 받은 학생
                dp[i][j][0] = dp[i-1][k][0]
                break
        dp[i][j][0] += 1
        if ans[0] < dp[i][j][0]:
            ans = [dp[i][j][0], dp[i][j][1]]  # 명수, 그레이드
        elif ans[0] == dp[i][j][0] and ans[1] > dp[i][j][1]:
            ans[1] = dp[i][j][1]  # 더 낮은 그레이드로

print(*ans)

 

이 문제는 같은 그레이드를 가진 학생이 몇 번 연속해서 나오는지 구해야 한다.

 

- grade[i]는 i번째 책상의 왼쪽과 오른쪽 학생의 그레이드이다.

- 각 책상까지 연속되는 그레이드와 학생 수를 저장할 배열 dp를 만든다. dp[i]는 2개의 리스트로 이루어지는데, 각각 i번째 책상의 왼쪽 학생과 오른쪽 학생까지 [grade[i][j]가 연속된 횟수, grade[i][j]]이다.

- dp[i]의 값은 dp[i-1]의 값을 이용해서 구해야 한다. i-1번째 책상에 나와 같은 그레이드를 받았던 사람이 있다면 그 사람까지 연속된 명수+1, 없다면 그냥 1이 dp[i][j][0]의 값이다.