Ridges and Valleys > 문제은행

본문 바로가기


실전대비 Level4

1302 : Ridges and Valleys

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 47 회    시도횟수: 115 회   



후연이는 도맹이와 함께 재미있는 놀이를 하고 있다. N×N의 체스 판 각각의 칸에 0 이상 1,000,000,000 이하의 정수를 적은 후, 아래와 같이 게임을 한다.

 

1) 두 사람은 번갈아 가며 체스 판의 수를 하나 선택한다. 이 수는 게임에서 선택되지 않은 수여야만 한다.

 

2) 선택된 수와 인접한 8칸에(혹은 경계라면 더 적을 수도 있음) 적힌 수들 중, 같은 수가 적힌 칸이 있다면 이 칸들도 선택한다. 이 작업은 새로 선택된 칸에도 반복하여 적용된다. 즉, 하나의 칸을 선택하면, 그 수에서 뻗어 나가면서 같은 수들이 적힌 칸들을 선택하게 된다.

 

3) 선택된 각각의 칸과 인접한, 선택되지 않은 칸에 적힌 수가 지금 선택한 칸들에 적힌 수보다 모두 작다면 후연이가 점수를 얻고, 모두 크다면 도맹이가 점수를 얻는다 (1점씩). 이 점수는 누가 선택했던, 작으면 후연이가, 크면 도맹이가 가져간다. 따라서 이 게임은 게임 시작과 동시에 점수가 정해지게 된다.

 

4) 자신이 점수를 얻을 수 있는 방법이 없다면, 다음 사람에게 차례가 돌아간다. 아래 예를 보자.

 

 e3050b66a1b29a01767400d7560a4131_1449730

 

파란 색으로 적힌 칸을 고르면 후연이가 점수를 얻고 빨간 색의 칸은 도맹이가 점수를 얻게 해준다. 위의 경우는 도맹이와 후연이 각각 3점씩 얻는다. 파랗게 된 7 중 어떤 것을 선택해도 1점을 얻게 된다. 첫 줄에 있는 7을 선택할 경우, 그 오른쪽 아래의 7과 함께 선택이 되는데, 주변에 적힌 수들이 5, 5, 5, 6, 6, 2, 6, 3, 8, 즉 7보다 모두 작거나 모두 크지 않기 때문에 둘 중 누구도 점수를 얻지 않는다.


첫 줄에 체스 판의 크기 N이 주어진다. N은 2 이상 1,000 이하의 자연수이다. 다음 N줄에 걸쳐 각 줄에 N개의 수가 주어진다. 수들은 0 이상 1,000,000,000 이하이다. 체스 판에 적힌 수가 모두 같은 경우는 주어지지 않는다.



첫 줄에 후연이의 점수와 도맹이의 점수를 차례로 출력한다.


[Copy]
5 
5 7 8 3 1 
5 5 7 6 6 
6 6 6 2 8 
5 7 2 5 8 
7 1 0 1 7
[Copy]
3 3





POI 2006/2007 Ridges and Valleys (Stage II - day 0)

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.