[BOJ] 21608 - 상어 초등학교 (Python)

 

 

아이디어

 

차례로 학생 자리를 교실에서 비어 있는 자리 중 규칙에 맞는 자리로 정하고, 학생의 만족도 총합을 구한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    N = int(input())
    classroom = [[0]*N for _ in range(N)]
    likes = [[] for _ in range(N**2+1)]
    for _ in range(N**2):
        student, *numbers = map(int, input().split())
        likes[student] = numbers
        max_like = max_empty = 0
        pos = []
        for r in range(N):
            for c in range(N):
                if classroom[r][c]:
                    continue
                like = empty = 0
                for dr, dc in delta:
                    if N > r+dr >= 0 and N > c+dc >= 0:
                        if classroom[r+dr][c+dc] in numbers:
                            like += 1
                        elif classroom[r+dr][c+dc] == 0:
                            empty += 1
                if like > max_like:
                    max_like = like
                    max_empty = empty
                    pos = [r, c]
                elif like == max_like and empty > max_empty:
                    max_empty = empty
                    pos = [r, c]
                elif not pos:
                    pos = [r, c]
        classroom[pos[0]][pos[1]] = student
    res = 0
    for r in range(N):
        for c in range(N):
            cnt = 0
            for dr, dc in delta:
                if N > r+dr >= 0 and N > c+dc >= 0:
                    if classroom[r+dr][c+dc] in likes[classroom[r][c]]:
                        cnt += 1
            if cnt:
                res += 10**(cnt-1)
    print(res)

solution()