10157 자리배정
난이도 : 실버 4
유형 : 구현
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번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.
6 7 8 9 10 11 12
5 26 27 28 29 30 13
4 25 38 39 40 31 14
3 24 37 42 41 32 15
2 23 36 35 34 33 16
1 22 21 20 19 18 17
여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다.
입력
첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.
출력
입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다.
풀이
달팽이문제였나? 그 문제처럼 접근하면 편하다. 4방향을 문제에 주어진 순서대로 정의하고 배열의 각 끝에 도달했을 때나 이미 값을 집어넣어준 곳에 도달했을 때 방향을 바꿔주는 방식으로 코드를 짜면된다.
대신 이건 값을 전부 넣어주지 않고 원하는 대기번호 K의 값까지만 넣으면 된다.
예외 N*M의 공연장에서 대기번호가 N*M보다 크게되면 이미 표를 받을 수 없기때문에 0을 출력해준다.
코드
package 구현;
import java.util.*;
/**
* BOJ_10157_S4_자리배정
* @author mingggkeee
* 구현
*/
public class BOJ_10157 {
static int C,R,K;
static int x,y; // 답 좌표
static int[][] map;
static int[][] dir = {{-1,0}, {0,1}, {1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
C = sc.nextInt();
R = sc.nextInt();
K = sc.nextInt(); // 찾아야하는 번호
map = new int[R][C];
if(R*C<K) {
System.out.println(0);
System.exit(0);
}
int count = 1;
int nx = R-1;
int ny = 0;
int direction = 0;
while(count != K) {
map[nx][ny] = count;
int tempx = nx + dir[direction][0];
int tempy = ny + dir[direction][1];
if(tempx<0 || tempy<0 || tempx>=R || tempy>=C || map[tempx][tempy] !=0) {
direction++;
if(direction==4) {
direction=0;
}
tempx = nx + dir[direction][0];
tempy = ny + dir[direction][1];
}
nx = tempx;
ny = tempy;
count++;
}
System.out.println((ny+1)+" "+(R-nx));
sc.close();
}
}
