탐사 > 문제은행

본문 바로가기


알고리즘 자료구조2

2614 : 탐사

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 91회    시도횟수: 1047회    Special Judge



직선 모양의 도로에 특별한 물체가 묻혀있다. 우리는 직선구간을 탐색할 수 있는 장비를 이용해서 이 물체가 어디에 있는지를 조사하고자 한다. 직선도로를 일차원 배열로 생각해보자. 아래 그림에서 숫자는 단위 구간의 번호이며 그 안에 ▲ 기호로 표시된 것은 우리가 찾아낼 물체이다.


7ce7f2eba5731c8babe39036322897a0_1449817 


그런데 우리는 어떤 연속된 구간에 포함되어 있는 물체의 개수를 Probe[x,y]를 이용하여 확인할 수 있다. x부터 y까지의 구간에 물체가 r개가 있음은 Probe[x,y]=r 로 표현된다(단 x≤y이다.) 예를 들어 그림 1과 같은 상황이라면 Probe[2,7]=3, Probe[2,2]=0, Probe[6,9]=4, Probe[5,12]=5 임을 알 수 있다.


여러분은 제시된 탐사작업의 결과가 모두 만족되는 구간을 재구성하는 프로그램을 작성해야 한다.


입력파일 첫 줄에는 두 개의 정수 K와 N이 주어져 있다. K는 전체 구간의 길이이며, N은 조사한 Probe[x,y]=r 결과의 개수이다. 
이어 나타나는 N개의 각 줄에는 하나의 탐사결과 Probe[x,y]=r 를 나타내는 세 개의 숫자 x, y, r 이 공백문자로 분리되어 제시되어 있다.
단 입력변수에 대한 제한 범위는 다음과 같다. 3≤K≤40, 2≤N≤1,000, 1≤x≤y≤K 이다.


여러분은 N개의 탐사결과를 만족하는 전체 구간을 길이 K 인 문자열로 표시해야 한다.

물체가 있는 단위 구간은 문자 ‘#’으로 표시해야 하고, 없는 단위 구간은 마이너스 기호 ‘-’로 표시해야 한다.

답이 여러 개 존재할 때에는 그 중 하나만 출력하면 된다. 만일 탐사결과를 모두 만족하는 답이 존재하지 않을 경우에는 문자열 “NONE"을 출력해야 한다.

[Copy]
12 7 
1 8 4 
6 10 4 
2 12 6 
9 12 2 
4 6 1 
1 4 1 
11 11 0
[Copy]
--#--####--#


[Copy]
12 2 
1 10 1 
4 7 3
[Copy]
NONE




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.