백준 - 10157번(자리배정)
문제 출처: https://www.acmicpc.net/problem/10157
문제
-
어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다.
-
예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다.
-
이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, 4, . 순으로 대기번호표를 받았다. 우리는 대기번호를 가진 사람들에 대하여 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 이것을 좀 더 구체적으로 설명하면 다음과 같다.
-
먼저 첫 번째 사람, 즉 대기번호 1인 사람은 자리 (1,1)에 배정한다. 그 다음에는 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 오른쪽에 더 이상 빈자리가 없으면 아래쪽으로 내려간다. 그리고 아래쪽에 더 이상 자리가 없으면 왼쪽으로 가면서 남은 빈 좌석을 배정한다. 이 후 왼쪽으로 더 이상의 빈 좌석이 없으면 다시 위쪽으로 배정하고, 이 과정을 모든 좌석이 배정될 때까지 반복한다.
-
아래 그림은 7×6공연장에서 대기번호 1번부터 42번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.
- 여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int M = scanner.nextInt(); // 가로
int N = scanner.nextInt(); // 세로
int K = scanner.nextInt(); // 타겟
boolean[][] visited = new boolean[N][M];
if (K > N * M) {
System.out.println(0);
return;
} else {
int[][] directions = {
{ 1, 0 },
{ 0, 1 },
{ -1, 0 },
{ 0, -1 },
};
int num = 1;
int index = 0;
int i = 0, j = 0;
visited[i][j] = true;
if (num++ == K) {
System.out.println((i + 1) + " " + (i + 1));
return;
} else {
while (num <= N * M) {
int dx = i + directions[index % 4][0];
int dy = j + directions[index % 4][1];
if (dx >= 0 && dx < N && dy >= 0 && dy < M && !visited[dx][dy]) {
visited[dx][dy] = true;
if (num++ == K) {
System.out.println((dy + 1) + " " + (dx + 1));
return;
}
i = dx;
j = dy;
continue;
} else {
index++;
}
}
}
}
}
}
- 달팽이 문제를 응용하여 풀 수 있었다.
- 우선 예시 사진을 상하 반전하여 배열의 인덱스에 대입하였다.
- 탐색 여부를 판단하는 boolean 배열을 하나 두고, 아래 -> 오른쪽 -> 위 -> 왼쪽 방향으로 돌아가며 회오리 모양으로 수를 배치하는 연산을 수행하며 입력된 값과 일치될 때의 인덱스를 출력하게 하였다.
Author And Source
이 문제에 관하여(백준 - 10157번(자리배정)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ghc1124/백준-10157번자리배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)