[Baekjoon] 10157_자리배정

Silver IV

문제(출처: https://www.acmicpc.net/problem/10157)

---

< 자리배정 >

 

문제 풀이 

 

왼쪽아래부터 시작하여 위, 오른쪽, 아래, 왼쪽 순으로 돌아가면서 좌석 번호를 지정한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _10157_ { // 자리배정

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int c = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(bf.readLine());

		if (c * r < k) {
			bw.write("0");
		} else {
			boolean arr[][] = new boolean[r][c];

			int x = r - 1, y = 0;
			int num = 1;
			arr[x][y] = true;

			int dx[] = { -1, 0, 1, 0 };
			int dy[] = { 0, 1, 0, -1 };
			int idx = 0;
			while (true) {
				if (num == k) {
					bw.write((y+1)+ " " + (r-x));
					break;
				}

				if (x + dx[idx] < 0 || x + dx[idx] >= r || y + dy[idx] < 0 || y + dy[idx] >= c
						|| arr[x + dx[idx]][y + dy[idx]]) {
					idx += 1;
					if (idx == 4) {
						idx = 0;
					}
				}
				x += dx[idx];
				y += dy[idx];
				arr[x][y] = true;
				num += 1;
			}
		}
		bw.flush();
	}
}

변수)
c, r, k : 격자 크기, 대기 번호
arr : 대기번호 배정 여부
x , y : 현재 위치
num : 현재 번호
dx, dy : 상하좌우
idx : 이동 방향

 

격자의 크기, 대기 번호를 입력받는다. 대기번호가 격자에 배정할 수 없는 번호라면 0을 출력한다. 배정할 수 있는 번호라면 격자에 1부터 값을 배정하며 좌석번호를 구한다. 왼쪽 아래부터 시작하기 위해 x, y를 각각 r-1과 0으로 초기화한다. arr [x][y]를 true로 바꿔 배정 완료로 저장한다. k번을 배정할 자리를 찾기 위해 다음 과정을 반복한다.

 

현재 배정할 값인 num이 대기번호 k과 일치하다면 배정될 좌석 번호를 찾은 것이므로 (y+1, r-x)를 출력하며 종료한다. 만약 num과 k값이 일치하지 않다면 현재 이동방향으로 이동할 경우를 생각하여 격자 크기를 벗어나거나, 이미 배정된 곳이라면 방향을 바꿔준다. 현재 이동 방향으로 이동한 후 arr[x][y]를 true로 저장하고 num 값을 1 더해준다.

---

* 처음에 k 값이 1일 때를 고려하지 않아 시간초과가 발생했다.

---