4802 : 자리배정
시간 제한: 1 Sec 메모리 제한: 512 MB제출: 18 해결 문제 수: 13
이 문제 1위 : kulong
문제2) 자리배정(초등3, 중등2, 고등1)
어떤 공연장에는 가로로 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번까지의 관객이 좌석에 배정된 결과를 보여주 고 있다.
여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x, y)를 찾는 프로그램을 작성 해야 한다.
첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다.
두 값의 범위는 5 ≤C, R≤1,000이 다.
그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤K ≤1,000,000,000이다.
여러분은 입력 파일에 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x, y)를 구해서 두 값, x와 y를 하나 의 공백을 사이에 두고 출력해야 한다.
만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석 을 배정할 수 없는 경우에는 0(숫자 영)을 출력해 야 한다.
7 6 11
6 6
입력2)
7 6
87
출력2)
0
입력3)
100 100
3000
출력3)
9 64
안녕하세요 방울입니다
정올 본선 준비하다가 문제를 푸는데
여기에 같이 풀까 합니다.
음음.. 근데 이거 어디서 본거같..
달팽이 배열이라고 몇년전(..)에 풀었던거같은데
블로그에도 없고 사라져버림
초심으로 다시 풉시다
팁을 하나 주자면
↓ 누르시면 펼쳐집니당.
하지만 팁 1을 사용하면 식상하기도 하고
그것이 문제가 아니라 저것은 정사각형일때만 이용할 수 있는 패턴이기때문에
이용하기에는 문제가 없지않아 있습니다.
그러므로 다른 방법을 이용할 겁니다.
↓ 누르시면 펼쳐집니당.
팁 2를 사용하여 풀겁니다.
제 방법이 절대 좋은 답안은 아닙니다.
각자 자신의 솔루션으로 풀어보시기 바랍니다.
↓ 누르시면 펼쳐집니당.
그리고 마지막인 모범 답안 입니다.
다 풀고나니 있더라고용
↓ 누르시면 펼쳐집니당.
푸는데 한 1시간 반정도 걸렸습니다.
이거 적으니까 몇시간쯤 걸리네요 ㅠㅠ
평일에 남는시간 쪼개서 풀겁니다
다음에 봅시다. 궁금한거 있으면 댓글 달아두세요
종종 와서 확인하고 가겠습니다.
