[백준10157번] 자리배정 파이썬 풀이

자리배정 

1 초

256 MB

14193

5377

4375

39.379%

문제

어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다. 

예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다. 

(1, 6)						(7, 6)
			(4, 4)			(7, 4)
(1, 3)					(6, 3)
(1, 2)
(1, 1)	(2, 1)	(3, 1)				(7, 1)

이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 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(숫자 영)을 출력해야 한다. 

예제 입력 1

7 6
11

예제 출력 1

6 6

예제 입력 2

7 6
87

예제 출력 2

0

예제 입력 3 

100 100
3000

예제 출력 3

9 64

 

구현, 브루트포스 알고리즘 문제이다.

행과 열의 최대 크기가 1000이므로, 배열의 모든 좌표를 문제에서 제시한 방향대로 방문하면서 몇번째 순번인지 확인후 원하는 대기순번인 K번에 도달할경우 좌표를 출력하면 된다.

 

중점적으로 구현해야 할 부분은 시계방향으로 방문하도록 하는 방법이다.

dx,dy를 사용하여 배열의 행과 열을 각각 조작하도록 하였고, 문제에서 배열의 형태가 왼쪽 아래부터 시작하므로, 구현의 편의를 위해 우리에게 익숙한 배열의 형태로 만들기 위해 왼쪽 아래를 기준으로 오른쪽으로 90도 회전시켰다.

바깥테두리부터 안쪽테두리까지 돌게 하기 위해 각 꼭짓점에 도달하는 기준점이 필요하였고 이를 위해 min_x,y, max_x,y를 사용하여 현재 시점에서의 최소값과 최대값을 두어 방향을 회전시키고 모든 테두리를 다 돌은 후 기준점들을 안쪽으로 이동시켰다.

 

자리를 배정할 수 없는 경우는 r*c를 초과하는 경우이므로 이러한 경우는 초기에 조건식을 통해 확인하고 다음단계로 나아가면 된다.

 

이 아이디어를 코드로 옮기면 아래와 같다.

 

# https://www.acmicpc.net/problem/10157
'''
구현, 브루트포스
최악의 경우에도 1000000번의 반복문
왼쪽 아래를 왼쪽 위로 생각하여 오른쪽으로 90도 회전해서 생각(우리에게 익숙한 배열의 형태)
(0,0),(0,1),(0,2),(0,3)..(0,c-1)
(1,0),(1,1),(1,2),(1,3)..(1,c-1)
(2,0),(2,1),(2,2),(2,3)..(2,c-1)
.................................
(r-1,0),(r-1,1),(r-1,2)..(r-1,c-1)
'''
c,r = map(int,input().split()) # c는 가로, r는 세로
k = int(input())
if k>c*r:
    print(0)
else:
    x,y,t,i = 1,1,1,3 # i는 현재 이동방향
    min_x,max_x,min_y,max_y = 1,c,1,r
    # 시계방향 이동 설정
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    count = 0
    while True:
        # 기준점 바꿔야 되는지 확인
        if count == 4 and (x,y) == (min_x,min_y):
            count = 0
            min_x+=1;min_y+=1
            max_x-=1;max_y-=1
            x,y = min_x,min_y
        if t==k:
            print(x,y)
            break
        if (x,y) == (min_x,min_y): # 왼쪽 위
            i+=1
            count+=1
        elif (x,y) == (min_x,max_y): # 오른쪽 위
            i+=1
            count+=1
        elif (x,y) == (max_x,max_y): # 오른쪽 아래
            i+=1
            count+=1
        elif (x,y) == (max_x,min_y): # 왼쪽 아래
            i+=1
            count+=1
        i%=4
        x += dx[i]
        y += dy[i]
        t+=1

 

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

10157번: 자리배정