기사 배치하기
문제
N×N의 보드 판에 K명의 기사가 배치되어 있으며, 기사들의 위치를 재배치하여 높은 점수를 얻고자 한다. 각 기사는 가만히 있거나 현재 위치를 기준으로 8가지 위치 중 하나로 이동할 수 있다. 이때 모든 기사는 각각 최대 한 번만 이동이 가능하며, 보드 판을 벗어날 수 없다. 또한 재배치 이후의 보드 판에서 한 위치(칸)에 두 명 이상의 기사가 존재할 수 없다.
초기 보드 판에서 기사가 존재하는 위치는 0으로 표시된다. 또한 기사가 존재하지 않는 곳은 모두 점수를 의미하는 값으로 0 초과의 수로 표시된다. 이때 점수의 값은 항상 1 이상 100 이하의 자연수다. 특정한 기사가 점수가 존재하는 칸(0 초과의 수를 가진 칸)으로 이동하는 경우 해당 값만큼 점수를 획득한다. 앞서 언급했듯이 각 기사는 초기 위치에서 원한다면 8가지 위치 중 하나로 이동할 수 있는데, 이동 방법은 체스 혹은 장기에서의 이동과 동일하다.
보드 판에서 각 칸의 위치를 (행, 열)의 형태로 표현하고, 인덱스는 0부터 시작한다고 가정하자. 한 명의 기사가 (3, 3)의 위치에 존재할 때, 해당 기사가 이동 가능한 위치를 그림으로 표현하면 다음과 같다. 구체적으로 (1, 2), (1, 4), (2, 1), (2, 5), (4, 1), (4, 5), (5, 2), (5, 4) 위치로 이동 가능하다. 그림으로 표현하면 다음의 그림과 같이 음영으로 칠해진 8가지 위치가 이동 가능한 위치다.
| ● | ● | |||||
| ● | ● | |||||
| 0 | ||||||
| ● | ● | |||||
| ● | ● |
위 표는 7행 7열 격자이며 기사(0)가 (3, 3)에 있다. 원본에서는 이동 가능한 8가지 위치가 음영으로만 표시되어 있어 텍스트 추출에서 셀 값이 남지 않았다. 본문에 적힌 위치 목록을 그대로 옮겨 ● 로 표시했다.
이어서 한 예시로 N=7, K=3인 상황을 가정해 보자. 아래 격자에서는 기사가 존재하는 위치에 대하여 음영 처리를 하였다.
| 2 | 0 | 6 | 5 | 7 | 8 | 4 |
|---|---|---|---|---|---|---|
| 5 | 7 | 7 | 8 | 7 | 4 | 5 |
| 8 | 5 | 9 | 6 | 5 | 9 | 6 |
| 7 | 9 | 4 | 5 | 0 | 8 | 7 |
| 9 | 8 | 5 | 9 | 7 | 8 | 8 |
| 7 | 0 | 7 | 4 | 3 | 7 | 4 |
| 7 | 9 | 9 | 5 | 8 | 4 | 3 |
앞서 언급했듯이, 각 기사는 이동을 하게 되면 자신이 이동한 위치에 적혀 있는 점수만큼 점수를 획득하게 된다. 우리의 목표는 기사들을 적절히 배치하여 얻을 수 있는 점수의 합을 최대로 만드는 것이다. 현재 예시에서는 (0, 1)에 위치한 기사가 (1, 3)의 위치로 이동하고, (3, 4)에 위치한 기사가 (2, 2)의 위치로 이동하고, (5, 1)에 위치한 기사가 (4, 3)의 위치로 이동하면 총 8 + 9 + 9 = 26의 값을 가진다. 이것이 모든 경우의 수를 고려했을 때, 얻을 수 있는(가능한) 최대 점수에 해당한다.
가능한 최대 점수를 얻을 수 있도록 해주는 기사의 도달 위치에 대하여 빨간색으로 음영 처리 하면, 다음 그림과 같다.
| 2 | 0 | 6 | 5 | 7 | 8 | 4 |
|---|---|---|---|---|---|---|
| 5 | 7 | 7 | 8 | 7 | 4 | 5 |
| 8 | 5 | 9 | 6 | 5 | 9 | 6 |
| 7 | 9 | 4 | 5 | 0 | 8 | 7 |
| 9 | 8 | 5 | 9 | 7 | 8 | 8 |
| 7 | 0 | 7 | 4 | 3 | 7 | 4 |
| 7 | 9 | 9 | 5 | 8 | 4 | 3 |
마찬가지로 3명의 기사가 (0, 1), (3, 4), (5, 1)의 위치에 존재하는 상황에서 이번에는 다음과 같이 각각 (0, 1), (1, 5), (6, 3)의 위치로 이동한다고 가정하자. (0, 1)의 위치에 존재하는 기사는 움직이지 않고, 가만히 있는 것을 선택한 것이다. 이 경우 점수의 총 합은 0 + 4 + 5 = 9로 오직 9점의 점수만을 얻을 수 있다. 이처럼 각 기사의 위치를 어떻게 선정하느냐에 따라서 얻을 수 있는 점수가 크게 달라질 수 있다.
| 2 | 0 | 6 | 5 | 7 | 8 | 4 |
|---|---|---|---|---|---|---|
| 5 | 7 | 7 | 8 | 7 | 4 | 5 |
| 8 | 5 | 9 | 6 | 5 | 9 | 6 |
| 7 | 9 | 4 | 5 | 0 | 8 | 7 |
| 9 | 8 | 5 | 9 | 7 | 8 | 8 |
| 7 | 0 | 7 | 4 | 3 | 7 | 4 |
| 7 | 9 | 9 | 5 | 8 | 4 | 3 |
결과적으로 보드 판의 정보가 주어졌을 때, 기사들을 적절히 배치함으로써 얻을 수 있는 점수의 합의 최댓값을 반환하는 프로그램을 작성하여라.
입출력 예시
예시 1
입력
7, 3, [[2, 0, 6, 5, 7, 8, 4], [5, 7, 7, 8, 7, 4, 5], [8, 5, 9, 6, 5, 9, 6], [7, 9, 4, 5, 0, 8, 7], [9, 8, 5, 9, 7, 8, 8], [7, 0, 7, 4, 3, 7, 4], [7, 9, 9, 5, 8, 4, 3]]
출력
26
입력 조건
가장 먼저 보드 판의 크기 N이 자연수로 주어진다. N은 5 이상 30 이하의 자연수다.
이어서 기사의 수 K가 자연수로 주어진다. K는 3 이상 7 이하의 자연수다.
이후에 N×N 크기의 보드의 정보가 담긴 배열 board가 주어진다. 초기 보드 판에서 기사가 존재하는 위치는 0으로 표시되며, 점수의 값은 항상 1 이상 100 이하의 자연수다.
출력 조건
K명의 기사를 적절히 배치하여, 얻을 수 있는 점수 합의 최댓값을 자연수 형태로 반환하여라.
요구사항
- solution(N, K, board) 함수를 만들고 답을 반환해야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 14개이고, 그 가운데 4개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 14개를 전부 통과해야 해결입니다.
예시
공개 케이스 4개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 14개를 전부 통과해야 해결입니다.
7, 3, [[2, 0, 6, 5, 7, 8, 4], [5, 7, 7, 8, 7, 4, 5], [8, 5, 9, 6, 5, 9, 6], [7, 9, 4, 5, 0, 8, 7], [9, 8, 5, 9, 7, 8, 8], [7, 0, 7, 4, 3, 7, 4], [7, 9, 9, 5, 8, 4, 3]]
26
18, 3, [[35, 39, 93, 56, 5, 42, 68, 55, 56, 6, 73, 4, 71, 2, 51, 21, 37, 86], [40, 58, 20, 16, 52, 62, 0, 86, 23, 80, 5, 93, 70, 68, 12, 65, 95, 87], [38, 77, 11, 56, 5, 11, 85, 18, 78, 86, 2, 47, 95, 93, 77, 56, 83, 88], [11, 64, 88, 71, 93, 64, 50, 25, 9, 46, 61, 50, 10, 89, 38, 8, 79, 58], [94, 2, 6, 18, 40, 60, 13, 82, 3, 37, 88, 15, 79, 92, 22, 30, 45, 58], [10, 75, 59, 41, 36, 92, 56, 77, 12, 91, 69, 5, 38, 11, 58, 95, 0, 43], [76, 20, 27, 3, 59, 24, 76, 18, 30, 17, 53, 95, 96, 12, 26, 88, 15, 21], [39, 84, 12, 65, 27, 61, 83, 8, 75, 64, 83, 80, 23, 31, 60, 21, 45, 93], [60, 10, 29, 32, 68, 99, 1, 100, 1, 14, 85, 45, 98, 48, 43, 92, 81, 51], [20, 89, 90, 47, 42, 0, 37, 5, 11, 54, 40, 4, 12, 69, 96, 77, 49, 14], [54, 85, 39, 43, 38, 26, 7, 86, 57, 33, 4, 50, 2, 46, 11, 79, 22, 76], [50, 33, 58, 41, 19, 23, 52, 45, 22, 37, 70, 93, 84, 97, 74, 86, 99, 24], [44, 83, 76, 33, 29, 35, 84, 98, 96, 70, 31, 40, 60, 3, 59, 100, 85, 74], [29, 26, 81, 69, 15, 34, 40, 7, 51, 50, 80, 13, 4, 69, 18, 64, 99, 97], [39, 100, 2, 19, 72, 4, 8, 11, 70, 29, 33, 91, 36, 89, 88, 23, 94, 30], [37, 16, 73, 9, 72, 43, 74, 21, 59, 60, 2, 72, 99, 96, 47, 2, 91, 68], [9, 35, 82, 26, 41, 56, 74, 94, 65, 73, ... 여기까지만 보여 드립니다 (전체 1,305자)
271
25, 7, [[52, 57, 36, 63, 3, 34, 44, 62, 2, 22, 50, 51, 13, 53, 93, 90, 22, 36, 33, 68, 40, 97, 72, 36, 28], [44, 13, 26, 79, 13, 34, 25, 6, 64, 65, 10, 56, 41, 87, 65, 95, 64, 70, 58, 83, 22, 67, 68, 88, 64], [74, 23, 29, 12, 47, 16, 47, 43, 91, 53, 20, 7, 15, 82, 58, 40, 35, 19, 90, 75, 42, 47, 39, 22, 19], [26, 18, 67, 64, 96, 15, 93, 38, 70, 5, 68, 74, 81, 92, 97, 27, 46, 31, 1, 86, 7, 0, 56, 44, 54], [66, 50, 8, 78, 61, 31, 50, 21, 27, 46, 89, 13, 20, 75, 65, 13, 76, 39, 60, 26, 90, 35, 73, 93, 16], [35, 66, 50, 58, 32, 96, 41, 81, 88, 100, 15, 2, 71, 23, 72, 1, 98, 92, 72, 45, 27, 82, 27, 63, 19], [17, 10, 61, 38, 34, 13, 82, 33, 62, 36, 57, 96, 21, 87, 51, 73, 37, 65, 58, 99, 51, 39, 87, 91, 51], [41, 23, 63, 81, 4, 78, 1, 74, 69, 89, 90, 82, 72, 97, 91, 6, 41, 8, 88, 11, 0, 38, 85, 97, 0], [99, 56, 15, 60, 35, 91, 89, 3, 56, 78, 85, 67, 20, 52, 7, 61, 42, 63, 74, 60, 82, 11, 80, 31, 21], [80, 87, 65, 16, 98, 84, 32, 32, 19, 45, 35, 4, 64, 26, 67, 71, 30, 3, 55, 81, 53, 97, 62, 78, 42], [59, 48, 86, 44, 84, 26, 6, 10, 62, 24, 84, 46, 80, 9, 11, 78, 65, 83, 58, 52, 30, 60, 68, 73, 36], [6, 71, 25, 52, 37, 40, 95, 24, 7, 79, 96, 93, 16, 13, 39, 92, 58, 98, 79, 17, 82, 84, 84, 6 ... 여기까지만 보여 드립니다 (전체 2,511자)
613
26, 4, [[75, 87, 64, 64, 75, 64, 96, 17, 11, 27, 38, 19, 46, 88, 64, 72, 11, 66, 93, 89, 52, 60, 18, 98, 6, 31], [47, 17, 4, 39, 21, 72, 88, 79, 53, 20, 36, 30, 88, 46, 64, 98, 27, 53, 39, 31, 36, 84, 70, 50, 56, 96], [15, 27, 14, 81, 19, 66, 63, 70, 78, 80, 92, 61, 36, 82, 97, 83, 50, 38, 94, 64, 89, 78, 72, 79, 61, 65], [79, 95, 59, 52, 97, 7, 64, 26, 28, 21, 48, 76, 36, 48, 89, 48, 86, 86, 69, 55, 29, 4, 100, 31, 66, 22], [42, 67, 23, 80, 56, 90, 54, 76, 64, 3, 44, 61, 16, 82, 88, 84, 81, 20, 49, 32, 20, 44, 83, 40, 48, 33], [79, 93, 1, 12, 52, 50, 9, 25, 78, 69, 40, 16, 79, 15, 96, 11, 58, 90, 99, 81, 2, 22, 16, 65, 8, 80], [0, 32, 51, 9, 81, 2, 18, 37, 31, 75, 68, 94, 68, 63, 68, 48, 99, 28, 94, 52, 85, 41, 67, 33, 5, 6], [24, 35, 79, 36, 53, 83, 99, 59, 95, 77, 63, 31, 23, 82, 53, 65, 51, 79, 89, 21, 50, 44, 49, 97, 25, 78], [87, 3, 66, 57, 96, 3, 71, 9, 85, 96, 34, 43, 47, 80, 7, 31, 58, 13, 21, 76, 40, 34, 6, 47, 69, 20], [56, 26, 55, 46, 19, 27, 70, 47, 80, 85, 66, 97, 42, 62, 84, 73, 13, 76, 50, 76, 72, 15, 56, 12, 32, 59], [37, 32, 21, 72, 100, 92, 92, 9, 51, 83, 83, 22, 33, 23, 58, 0, 64, 30, 89, 94, 47, 33, 87, 97, 91, 68], [49, 85, 39, 25, 79, 41, 12, 43, 31, 78, 62, ... 여기까지만 보여 드립니다 (전체 2,708자)
340
참고 사항
풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.
원본에서 모의고사 7회 3번입니다.
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 4개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.