문제 링크

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

문제 설명

• 앉으려는 학생의 순서와, 학생마다 좋아하는 학생 4명의 번호가 주어짐
• 순서대로 좋아하는 학생이 주변에 많거나, 빈 자리가 많은 자리에 앉는다
• 총 만족도를 출력

풀이

• 학생마다 순서대로 돌면서
• 각 자리의 주변의 좋아하는 학생 수, 빈 자리 수를 카운트
• 최대 위치를 기록해서 해당 위치에 앉는다
• 모두 앉은 후 다시 한번 돌면서 만족도를 계산

코드

import sys
read = sys.stdin.readline
n = int(read())
orders = []
like = [set() for _ in range(n**2+1)]
for _ in range(n**2):
    num, a,b,c,d = map(int, read().split())
    orders.append(num)
    like[num] = set([a,b,c,d])
board = [[0]*(n+1) for _ in range(n+1)]
dy, dx = [1,-1,0,0], [0,0,1,-1]

# 순서대로
for num in orders:
    # 최대 위치 찾기
    max_like, max_empty = -1, -1
    my, mx = 100, 100
    for cy in range(1, n+1):
        for cx in range(1, n+1):
            if board[cy][cx] != 0:
                continue
            # 좋 개수, 빈 개수 세기
            like_count, empty_count = 0, 0
            for d in range(4):
                ny, nx = cy+dy[d], cx+dx[d]
                if 1<=ny<=n and 1<=nx<=n:
                    if board[ny][nx] in like[num]:
                        like_count += 1
                    elif board[ny][nx] == 0:
                        empty_count += 1
            # 최대이면 갱신
            if max_like < like_count:
                max_like, max_empty = like_count, empty_count
                my, mx = cy, cx
            elif max_like == like_count:
                if max_empty < empty_count:
                    max_like, max_empty = like_count, empty_count
                    my, mx = cy, cx
    board[my][mx] = num

# 만족도 구하기
answer = 0
for cy in range(1, n+1):
    for cx in range(1, n+1):
        num = board[cy][cx]
        # 좋 개수, 빈 개수 세기
        like_count = 0
        for d in range(4):
            ny, nx = cy+dy[d], cx+dx[d]
            if 1<=ny<=n and 1<=nx<=n:
                if board[ny][nx] in like[num]:
                    like_count += 1
        if like_count > 0:
            answer += 10 ** (like_count-1)

print(answer)