상어초등학교는 N*N크기의 격자로 이루어진 교실이 있다. 학생은 1번부터 N^2번까지 N^2명이다.
선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 한칸에 한명의 학생만 있을 수 있을때, 다음과 같은 규칙으로 자리를 배정한다.
자리를 정하고는 만족도 조사를 한다. 각 학생별 인접한 칸에 앉은 좋아하는 학생의 수에 따라 만족도가 결정된다. 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
학생의 만족도의 총 합은?
이게 상반기 오전 1번이랬나,, 암튼
각 학생당 좋아하는 학생의 번호는 dictionary를 사용해서 저장했다.
students[i]
: i번 학생이 좋아하는 학생 번호 리스트
N = int(input())
students = defaultdict()
for _ in range(N**2):
num, s1, s2, s3, s4 = map(int, input().split())
students[num] = [s1,s2,s3,s4]
board = [[0 for _ in range(N)] for _ in range(N)]
모든 학생에 대해서 (0,0)부터 (N-1,N-1)까지 돌면서 가장 많은 수의 좋아하는 친구와 인접하고, 그 중 인접한 빈칸이 제일 많으며 그 중에서 제일 왼쪽 위에 있는 칸을 고른다.
각 학생에 대해서 cur_max = [-1, -1, -1, -1] # likes, empty, x, y
를 이용해서 현재까지 조사한 칸 중 제일 적합한 칸을 저장했다.
처음에는 cur_max의 좌표값을 (0,0)으로 뒀더니 ,, 자리를 배정받지 못하는 학생이 생겨서 계속 Key Error가 났다 ㅠㅠ 실제 시험이었으면 어디서 틀렸는지 찾기 힘들었을듯 ^_ㅠ
# 1. 자리 정하기
for s in students.keys():
# 모든 학생에 대해서
cur_max = [-1, -1, -1, -1] # likes, empty, x, y
for i in range(N):
for j in range(N):
if board[i][j] == 0:
# 빈칸이면
likes, empty = 0, 0
for k in range(4):
ni, nj = i+dx[k], j+dy[k]
if in_bound(ni,nj):
if board[ni][nj] in students[s]:
likes += 1
elif board[ni][nj] == 0:
empty += 1
if likes > cur_max[0]:
cur_max = [likes, empty, i, j]
elif likes == cur_max[0] and empty > cur_max[1]:
cur_max = [likes, empty, i, j]
board[cur_max[2]][cur_max[3]] = s
# 2. 만족도 구하기
answer = 0
for i in range(N):
for j in range(N):
count = 0
num = board[i][j]
for k in range(4):
ni, nj = i+dx[k], j+dy[k]
if in_bound(ni,nj):
if board[ni][nj] in students[num]:
count += 1
if count != 0:
answer += 10**(count-1)
만족도는 위와 마찬가지로 (0,0), (N-1,N-1)까지의 자리를 돌면서 인접한 4칸을 조사한다.
import sys
from collections import defaultdict
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def in_bound(x, y):
if x in range(N) and y in range(N):
return True
return False
N = int(input())
students = defaultdict()
for _ in range(N**2):
num, s1, s2, s3, s4 = map(int, input().split())
students[num] = [s1,s2,s3,s4]
board = [[0 for _ in range(N)] for _ in range(N)]
# 1. 자리 정하기
for s in students.keys():
# 모든 학생에 대해서
cur_max = [-1, -1, -1, -1] # likes, empty, x, y
for i in range(N):
for j in range(N):
if board[i][j] == 0:
# 빈칸이면
likes, empty = 0, 0
for k in range(4):
ni, nj = i+dx[k], j+dy[k]
if in_bound(ni,nj):
if board[ni][nj] in students[s]:
likes += 1
elif board[ni][nj] == 0:
empty += 1
if likes > cur_max[0]:
cur_max = [likes, empty, i, j]
elif likes == cur_max[0] and empty > cur_max[1]:
cur_max = [likes, empty, i, j]
board[cur_max[2]][cur_max[3]] = s
# 2. 만족도 구하기
answer = 0
for i in range(N):
for j in range(N):
count = 0
num = board[i][j]
for k in range(4):
ni, nj = i+dx[k], j+dy[k]
if in_bound(ni,nj):
if board[ni][nj] in students[num]:
count += 1
if count != 0:
answer += 10**(count-1)
print(answer)
30분