2015년 전국대비 1회 해법 > 공지게시판

본문 바로가기


정올소식

커뮤니티

정올소식
자유게시판
질문게시판
자주하는질문(FAQ)

2015년 전국대비 1회 해법

페이지 정보

작성자 관리자 작성일15-06-13 17:42 조회878회 댓글0건

본문

 

두 수학자
 
집으로 들어간 사람보다 나온 사람이 얼마나 많은지 확인해 보면 된다.
즉 집으로 들어간 사람의 합보다 나온 사람의 합이 더 크다면 처음에 최소한 그 인원만큼 있었을 것이다. 각 단계마다 최소한 인원을 구해서 그중 최대값을 출력하면 된다.
 
예제의 첫 번째 케이스를 보면
3명이 들어가서 5명이 나왔다면 처음에 최소한 2명은 있었을 것이다.
그리고 다시 3명이 들어가서 4명이 나왔다면 총 6명이 들어가서 9명이 나온 것이므로 최소한 3명은 있었을 것이다.
마지막으로 1명이 들어가서 1명이 나왔다면 총 7명이 들어가서 10명이 나온 것이므로 최소한 3명은 있었을 것이다.
따라서 최소한 3명이 있었다는 것을 알 수 있다.
 
두 번째 케이스를 보면
3명 들어가서 5명 나왔으므로 최소한 2명이 있었을 것이고
4명 들어가서 7명 나왔으므로 총 7명 들어가서 12명 나온 것이므로 최소한 5명 있었을 것이고
5명 들어가서 1명 나왔으므로 총 12명 들어가서 13명 나온 것이므로 최소한 1명 있었을 것이고
1명 들어가서 2명 나왔으므로 총 13명 들어가서 15명 나온 것이므로 최소한 2명 있었을 것이다.
위에서 최소한 있었던 인원의 최대값은 5명이다.
 
모기 덫
 
X좌표의 최대값과 최소값의 차를 구하고
Y좌표의 최대값과 최소값의 차를 구해서
더 큰 값을 한변으로 하는 정사각형의 넓이를 구하면 된다.
 
 
마피아
 
일단 여러 가지 경우가 발생할 수 있지만 한 번도 지목을 받지 않은 사람을 마피아라고 가정하는 경우가 마피아로 추측되는 최대 인원이 될 수 있다.
 
입력예 3의 경우를 가정해보면
1번과 2, 7번은 한번도 지목을 당하지 않았으므로 일단 마피아로 가정을 한다.
그러면 이들이 지목한 3번과 4번은 마피아가 아니다.
이렇게 결정된 5명을 제외하고 남은 인원으로 다시 반복을 한다.
남은 5번과 6번을 보면 5번은 6번을 지목했지만 5번은 지목되지 않았으므로 5번이 마피아이고 6번은 마피아가 아닌 것이다.
 
만약 입력예 2와 같이 한 번도 지목되지 않은 사람이 없다면 사이클이 발생한 것이므로 사이클을 찾아 그중 1/2을 마피아로 처리하면 된다.
 
 
분수 수열
 
만약 분모가 1이라면 가장 오른쪽에 있는 것이므로 오른쪽 자식을 구하여 분모와 분자를 바꾸면 된다. ) 2/1 이라면 오른쪽 자식은 3/1, 분모분자를 바꾸면 1/3이 된다.
 
만약 분모가 더 크다면 왼쪽 자식에 해당하므로 부모를 찾아서 오른쪽 자식의 크기를 구하면 된다. ) 2/3 부모는 2/1, 오른쪽 자식은 3/1
 
분자가 크다면 오른쪽 자식이므로 오른쪽 부모를 만날 때까지 올라가서 오른쪽 자식을 구한 후 왼쪽으로 올라간만큼 다시 왼쪽으로 내려가면 된다.
) 5/2 - 왼쪽부모 3/2 - 왼쪽부모 1/2 - 오른쪽 부모 1/1 - 오른쪽 자식 2/1 - 왼쪽 자식 2/3 - 왼쪽자식 2/5
 
 
소음줄이기
 
각 건물에 입주하는 인원의 합을 구하고 소음레벨의 합과 한번을 비우면 줄어드는 소음레벨의 값을 각각 구한다.
소음레벨이 가장 많이 줄어드는 건물부터 차례대로 건물비우는 횟수를 배정한다. 건물을 비우는 횟수가 증가하게 되면 소음레벨의 합과 다시 한번 건물을 비울 때 줄어드는 소음레벨의 값을 새로 구해야 한다.
위와 같은 작업을 K번 반복한 후 각 건물의 소음레벨의 합을 출력하면 된다.
 
참고로 건물에 입주하는 인원수를 x, 건물을 비우는 횟수를 y 라 하면, 1부터 i까지의 합을 s[i]라고 할 때 각 건물의 소음레벨을 구하는 식은 s[x/y] * y + x%y * (x/y+1) 이 된다.
 
 
본부를 어디에 세울까?
 
홍수가 난 마을간 모든 거리를 구한다. (어느 한 마을을 호출하여 DFS로 구할 수 있다.)
홍수가 난 마을과 홍수난 마을 사이에 끼어있는 마을은 자신과 가장 멀리 떨어진 홍수난 마을까지의 거리를 구하여 전체거리 * 2 - 최장거리가 해당 마을의 출력값이다.
그렇지 않은 마을은 가장 가까운 홍수난 마을을 찾아서 그 마을의 출력값에 그 마을까지의 거리를 더한 값을 출력하면 된다.
모든 마을마다 최장거리를 구하려고 하면 시간초과가 발생할 수 있으므로 홍수난 마을중 최장거리를 먼저 구하여 양쪽 끝 마을부터 모든 마을까지의 최장거리를 한번에 구해놓으면 시간내에 결과값을 구할 수 있다.

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.