[ 백준 10157 ] 자리배정

 

난이도 : S3

Link  : https://www.acmicpc.net/problem/10157

Tag : 시뮬레이션/구현

 

문제 탐색하기 

- 달팽이 처럼 순서대로 자리를 배정할 때 특정 k번째의 사람이 어디에 위치 하냐

 

시도 1 ( 성공 😲)

시간복잡도⏰

차례대로 모든 위치를 배정하면 가능합니다. 

숫자 k는 최대 1억으로 매우 큰 숫자이지만 C, R은 1000이하로 제한되어있으므로 모든 사람들을 배정한다 하더라도

1000*1000 = 1,000,00 로 시간내에 해결할 수 있습니다. 또한 만약 C*R의 좌석 크기보다 K가 크다면 0으로 바로 출력할 수 있습니다.

 

시간복잡도 계산

모든 자리를 배정하다가 k번째 되면 해당 위치를 출력해주면 됩니다. 최악의 경우 C*R번째의 사람의 위치를 출력하는 것이기 때문에 최대 자리 크기 C*R = 1,000,000 으로 시간내에 해결할 수 있을것입니다.

 

구현 방법 

세부 구현 사항

1. 주어진 값들을 입력 받습니다. 

2. 반복해서 해당 방향으로 이동시킨다.

3. 만약 이미 방문 했거나, 크기를 벗어날 경우 방향을 틀어서 다시 이동시킨다.'

 

import java.io.IOException;
import java.util.*;

class Main {
    private static int[] dirX = { 0, 1, 0, -1 };
    private static int[] dirY = { 1, 0, -1, 0 };

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();
        int r = sc.nextInt();
        int k = sc.nextInt();
        if (k > c * r) {
            System.out.println(0);
            return;
        }

        int[][] visit = new int[r][c];
        int dir = 0;
        int x = 0;
        int y = 0;
        int now = 1;
        visit[y][x] = 1;

        while (now < k) {
            int dx = x + dirX[dir];
            int dy = y + dirY[dir];
            if (dx < 0 || dx >= c || dy < 0 || dy >= r || visit[dy][dx] == 1) {
                dir = (dir + 1) % 4;
            } else {
                now++;
                x = dx;
                y = dy;
                visit[y][x] = 1;
            }
        }
        System.out.println((x + 1) + " " + (y + 1));
    }
}

 

문제에서는 가장 밑에서부터 자리를 배치하여 왼쪽 밑이 (1,1)로 시작되었지만 구현상 편의를 위해 뒤집어서 (1,1)이 왼쪽 위에서 시작되도록 구현하였습니다. 결과는 변화 없습니다.

 

 

 

마무리

구현은 난이도가 올라갈 수록 급격하게 어려워지는 것 같습니다.

요즘 중요하게 여기는 문제 유형인만큼 많은 연습이 필요할 것 같습니다.