3
4 2 5 1 7
3 1 9 4 5
9 8 1 2 3
8 1 9 3 4
7 2 3 4 8
1 9 2 5 7
6 5 2 3 4
5 1 9 2 8
2 9 3 1 4

54

3
4 2 5 1 7
2 1 9 4 5
5 8 1 4 3
1 2 9 3 4
7 2 3 4 8
9 8 4 5 7
6 5 2 3 4
8 4 9 2 1
3 9 2 1 4

1053

삼성 역량테스트의 '상어 시리즈' 문제이다.

별다른 알고리즘을 요구하지 않고 단순히 문제에서 요구하는대로 구현하면되는 문제이다. 굳이 문제의 분류를 하자면 구현, 정렬, 등이 있겠다.

구현 문제는 문제에서 주어진 순서에 맞춰 차례대로 코드를 구현하고 함수를 실행하면 된다.

문제의 요구사항을 아래와 같이 간략화 시켜보았다.

#0. 모든 칸을 순위하며 해당 학생이 앉을 자리 찾기

#1. 인접한 칸 중 해당 학생이 좋아하는 학생의 수와, 빈 칸의 수를 배열에 각각 기록

#1.1. 배열에 기록할 값 => (좋아하는 학생의 수, 빈 칸의 수, 행의 번호, 열의 번호)

#2. 배열을 조건1~3에 맞춰 정렬한 후, 조건을 만족하는 자리에 배치

#3. 모든 학생들을 배치한 후, 배열을 돌면서 전체 만족도 계산

문제의 요구사항에 따르면 학생들을 배치하는 과정은 아래와 같은 순서를 따른다.

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

따라서 위 3조건을 만족하는 모든 좌표를 배열에 기록해둔다음 위 조건에 맞춰서 배열을 정렬시킨후 가장 앞서는 값의 좌표를 학생이 앉을 좌표로 설정하면 된다.

파이썬에서 정렬은 sorted와 sort로 수행되며 위 문제에서 처럼 정렬 기준을 사용자가 원하는 기준대로 설정하기 위해선 람다식을 사용해야한다.

예를 들어 배열에 저장된 형태가 (좋아하는 학생의 수, 빈 영역의 수, 행의 번호, 열의 번호) 라면, 좋아하는 학생 수와 빈 영역의 수는 내림차순으로 정렬하고, 좌표값은 내림차순으로 정렬해야 하므로 아래와 같이 -기호를 사용하여 정렬 기준을 설정한다.

seat_info.sort(key = lambda x: (-x[0],-x[1],x[2],x[3]))

위와 같이 작성한다면 x의 0,1,2,3번째 인덱스의 값을 바탕으로 정렬을 수행하며 앞에 위치하는 인덱스가 정렬에서 우선시 되며 뒤에 위치하는 인덱스는 동일한 값이 있을 경우에 대한 정렬기준이 된다.

이 아이디어들을 코드로 옮기면 아래와 같다.

# https://www.acmicpc.net/problem/21608
N = int(input())
seat = [[0]*N for _ in range(N)]
dx = [0,0,-1,1]
dy = [-1,1,0,0]

# n번째 학생이 앉을 자리 계산
def select_seat():
    global seat
    # 각 좌석에 대한 정보를 기록하기 위한 배열 생성
    seat_info = []
    for x in range(N):
        for y in range(N):
            if seat[x][y] != 0:
                continue
            like_count,empty_count = 0,0 # 좋아하는 학생수, 빈좌석수
            # 앉을 수 있는 자리에 대해서 상하좌우 검사
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<N:
                    if seat[nx][ny] in like: # 좋아하는 학생이라면
                        like_count+=1
                    elif seat[nx][ny] == 0: # 빈 좌석이라면
                        empty_count+=1
            # 현재 좌석에 대한 정보 배열에 기록
            seat_info.append([like_count,empty_count,x,y])
    
    # 최적의 자리 계산하여 배치
    # 1. 좋아하는 사람이 가장 많은 자리로
    # 2. 그 중에서 주변에 빈칸이 많은 자리로
    # 3. 그 중에서 행의 번호가 가장 작고, 그 다음으로 열의 번호가 가장 작은 순으로
    # 내림차순,내림차순,오름차순,오름차순
    seat_info.sort(key = lambda x: (-x[0],-x[1],x[2],x[3])) 
    
    # 정렬 이후 가장 왼쪽에 위치한 값의 x,y좌표
    x = seat_info[0][2]
    y = seat_info[0][3]
    
    # 그 좌표에 사람 배치
    seat[x][y] = n


# 전체 만족도 계산
def calc_satisfication():
    result = 0 # 만족도 총합
    for x in range(N):
        for y in range(N):
            p = seat[x][y] # 그 칸에 있는 사람의 번호
            like = people[p] # 그 사람이 좋아하는 사람들
            like_count = 0 # 좋아하는 사람의 수
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<N:
                    if seat[nx][ny] in like:
                        like_count += 1
            if like_count == 1:
                result += 1
            elif like_count == 2:
                result += 10
            elif like_count == 3:
                result += 100
            elif like_count == 4:
                result += 1000
    return result

people = [[] for _ in range(N*N+1)] # N번 사람이 각각 누구를 좋아하는지 기록 => 호감도 계산에 사용
for _ in range(N*N):
    data = list(map(int,input().split()))
    n,like = data[0],data[1:]
    people[n] = like
    select_seat()

print(calc_satisfication())

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

문제

준성이는 1㎝ 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다.

준성이는 먼저 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또 다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다.

예를 들어 길이 10㎝ 인 줄자에 아래 그림과 같이 2㎝ 와 7㎝ 위에에 두 빨간 점이 찍혀 있고, 5㎝ 와 4㎝위치에 파란 점이, 10㎝ 와 3㎝ 위치에 노란 점이 찍혀 있다고 하자. (그림에서 빨간 점은 별표로, 파란 점은 동그라미, 그리고 노란 점은 네모로 표시되어 있다.) 빨간 두 점이 만나도록 줄자를 접으면 줄자의 4.5㎝ 위치에서 접히고 4㎝ 와 5㎝ 눈금이 서로 만나게 된다. 그러면 줄자의 왼쪽 부분의 길이는 4.5㎝ 이고 오른쪽 부분의 길이는 5.5㎝가 되어, 접힌 줄자의 길이는 5.5㎝ 가 된다. 파란 두 점은 이미 만나므로 줄자를 접지 않고, 그런 다음 노란 두 점이 만나도록 접으면 줄자의 길이는 3.5㎝ 가 된다.

줄자의 길이와 각 색깔의 점들이 찍혀있는 위치가 주어질 때, 준성이가 빨간 색, 파란 색, 노란 색의 순서로 두 점이 만나도록 줄자를 접으면 줄자의 길이가 얼마가 되는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄자의 길이가 입력된다. 줄자의 길이는 10㎝ 이상, 1,000㎝ 이하이고 단위를 나타내는 ㎝은 입력되지 않는다. 둘째 줄에는 두 빨간 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 셋째 줄에는 두 파란 점의 위치가, 넷째 줄에는 두 노란 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 모든 점들의 위치는 서로 다르다.

출력

한 줄에 접은 후의 줄자의 길이를 소수점 이하 한자리까지 출력한다. 소수점 이하 한자리가 0 이면 0 도 출력한다.(예 4.0)

예제 입력 1 

10
2 7
5 4
10 3

예제 출력 1 

3.5

약간의 수학과 구현 알고리즘으로 해결할 수 있는 문제이다.

'접는다' 라는 개념이 낯설게 느껴져 다소 고민을 했었지만 차근차근 생각하면 된다.

먼저 접는 순서는 빨강 -> 파랑 -> 노랑의 순서를 가지며, 접은 후의 길이는 접힌 부분과 접히지 않는 부분의 길이 중 더 긴 길이를 채택한다.

예를 들어 문제와 같이 4.5를 기준으로 접을때 아래와 같은 모양이 될 것이다.

위는 기존의 위치이고, 아래는 접힌 부분을 표시한 것이다. 4.5~10까지의 길이가 더 길기 때문에 전체 종이의 길이는 10-4.5가 된다.

그럼 이제 점들의 좌표를 어떻게 변경할까의 문제이다.

문제의 예시를 기준으로 빨간점 (2,7)이 접혔을때의 중간지점(접히는 지점)을 알기 위해 두 수의 평균을 구한다.

=> (2 + 7 )/ 2 = 4.5

4.5라는 좌표를 기준으로 두 점을 접게되므로, 다른점들도 새로운 좌표로 이동하게 되는데 여기서 당연하게도 접히는 지점보다 오른쪽에 있는 수들은 움직이지 않고 위치가 고정될 것이다. 위 예시에서 파란점5, 빨간점7, 노란점10이 이에 해당한다.(4.5<5, 7, 10)

새로운 좌표는 대칭 이동이므로, 기준점(위 예시에서는 빨간색 점)들의 합에 맞춰 대칭이동을 수행하면 된다.

따라서 파란점 4는 9(2+7) - 4 한 값인 5로 이동하게 될 것이며, 노란점 3은 9 - 3 = 6이므로 좌표 6으로 이동하게 된다.

위 알고리즘을 적용한 다른 예시는 아래와 같다. 편의상 빨,파,노는 r,b,y로 적었다.

0 1 2 3 4 5 6 7 8 9 10
    b b   y y r r 

# r 접기
7+8 = 15, 중간점 7.5, 전체 길이 (10-7.5 = 2.5) < (7.5-0 = 7.5) => 7.5
7.5 8 9 10 11 12 13 14 15
    r y  y     b  b

# b 접기
12 + 13 = 25, 중간점 12.5, 전체 길이 (15-12.5 = 2.5) < (12.5-7.5 = 5) => 5
12.5 13 14 15 16 17 17.5
b           y  y

# y 접기
15 + 16 = 31, 중간점 15.5, 전체길이 (17.5-15.5=2) < (15.5-12.5=3) => 3

이 알고리즘을 코드로 옮기면 아래와 같다. 편의를 위해 반복문을 사용하여 중복을 최소화하였다.

start = 0 # 시작 좌표는 0
end = int(input()) # 끝 점의 좌표
length = end-start+1
colors = [list(map(int,input().split())) for _ in range(3)]
for i,color in enumerate(colors):
    # 만약 두 점의 좌표가 같다면 해당 색상에 대해서는 이동하지 않는다.
    if color[0] == color[1]:
        continue
    # 중간점 구하기
    color_sum = sum(color)
    mid = round(color_sum/2,1) # 소수점 첫째자리까지
    # 전체 길이 구하기
    length = max((end-mid),(mid-start))
    # 새로운 시작점, 끝점 구하기
    start = mid
    end = start + length
    # 좌표 이동
    # 현재 움직인 좌표 이후의 색에 대해서만
    for j in range(i,len(colors)):
        for k in range(2):
            if colors[j][k] < mid: # 중간점보다 왼쪽에 있는 경우에만 새로운 좌표로 움직인다.
                colors[j][k] = color_sum - colors[j][k]
print(length)

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