[백준] 10157 - 자리배정 (C++)

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

좌석이 C × R 격자형으로 배치된 공연장이 있고, 각 좌석의 번호는 (x, y)로 표시된다. 대기번호를 가진 사람들에 대해 (1, 1) 좌석부터 시작해 시계 방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 비어있는 공연장의 크기를 나타내는 자연수 C, R이 주어져 있을 때, 대기번호가 K인 관객에게 배정될 좌석 번호 (x, y)를 찾는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 5 ≤ C, R ≤ 1,000
• 1 ≤ K ≤ 100,000,000
• 모든 좌석이 배정돼 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우 0 출력

 

공연장의 최대 크기만큼 방문 여부를 저장할 bool 배열을 만든다.

K가 배정할 수 있는 좌석 개수보다 크면 0을 출력해야 하고, K가 1일 때는 (1, 1)을 출력해야 한다. 이 두 경우가 아니면 반목문으로 좌석 번호(정수값)가 K와 같을 때까지 진행한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. R, C, K 입력받기 (보통 행은 R, 열은 C로 표현해서 헷갈릴까 봐 바꿔서 입력받기)
2. R * C가 K보다 작거나 K가 1인 경우를 예외로 두기
3. 초기값과 반목문을 통해 시계 방향으로 돌려가면서 num이 K와 같아질 때까지 반복
4. 좌석번호 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
using namespace std;

int c,r,k,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool board[1001][1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();

    cin >> r >> c >> k;
    
    if (c * r < k) {
        cout << 0;
    }
    else if (k==1) {
        cout << 1 << ' ' << 1;
    }
    else {
        int x=1,y=1,d=0,num=1;
        board[x][y]=true;
        while (1) {
            int cx=x+dx[d],cy=y+dy[d];
            if (cx>r || cx<=0 || cy>c || cy<=0 || board[cx][cy]) d = (d+1) % 4;
            x += dx[d];
            y += dy[d];
            board[x][y] = true;
            num++;
            if (num==k) break;
        }

        cout << x << ' ' << y;
    }
}