[BOJ] 21608 - 상어초등학교

김우경·2021년 5월 3일
0

삼성기출

목록 보기
34/37

문제링크

21608 - 상어초등학교

문제설명

상어초등학교는 N*N크기의 격자로 이루어진 교실이 있다. 학생은 1번부터 N^2번까지 N^2명이다.

선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 한칸에 한명의 학생만 있을 수 있을때, 다음과 같은 규칙으로 자리를 배정한다.

  1. 빈칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
  2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
  3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

자리를 정하고는 만족도 조사를 한다. 각 학생별 인접한 칸에 앉은 좋아하는 학생의 수에 따라 만족도가 결정된다. 값이 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분

profile
Hongik CE

0개의 댓글