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

본문 바로가기


정올소식

커뮤니티

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

2015년 전국대비 2회 해법

페이지 정보

작성자 관리자 작성일15-06-22 16:15 조회2,011회 댓글0건

본문

 

사탕공장
 
간단한 계산식으로 풀 수 있다.
각 기계마다 시간당 만들 수 있는 사탕의 개수 * 기계의 수를 모두 구한 후 시간을 곱해주면 된다.
sum (60 / Mi * Ci) * H
 
 
챔피언스리그 준준결승
 
A팀의 점수와 B팀의 점수를 합산해서 점수가 높은팀은 현재상태로 끝나면 되므로 0을 출력한다.
그렇지 않은 팀은 일단 동점을 만들기 위해 필요한 점수를 더한 다음 원정득점이 더 많으면 더한 점수를 그대로 출력하고 그렇지 않으면 더한점수 + 1을 출력하면 된다.
 
 
체스보드 개수세기
 
좌표의 (8, 8)부터 마지막까지에서 흰색의 개수가 몇 개인지 구하는 것과 같다.
(8, 8)부터 마지막까지의 전체 개수는 (H - 7) * (W - 7) 개다.
그 중 흰색의 개수는 반이므로 2로 나누면 된다.
만약 전체개수가 홀수라면 마지막 색이 한 개 더 많은 것이므로 C를 더하면 된다.
두 줄의 식으로 나타내면 다음과 같이 쓸 수 있다.
ans = (H - 7) * (W - 7);
ans += (ans % 2) * C;
 
 
뒤집기 게임
 
입력받은 것을 모두 0이 되도록 바꾸면 된다.
가장 왼쪽 위에서부터 차례대로 탐색하면서 1인 것이 나오면 그 위치부터 사회자가 부른 행과열의 크기만큼 바꾸어준다. 보드의 높이 N, 너비 M, 그리고 사회자가 부르는 행과 열의 범위가 R, C일 경우
(N - R + 1, M - C +1) 까지 모두 바꾸어 준 후 1이 남아있다면 -1을 출력하고 그렇지 않은 경우 바꾼 횟수를 출력하면 된다.
 
 
최빈값 알아보기
 
인덱스트리 또는 세그먼트트리를 이용하여 해당범위의 왼쪽 숫자의 개수(lcnt), 오른쪽 숫자의 개수(rcnt), 최대숫자의 개수(maxcnt)를 저장한다.
구간 A의 왼쪽 자식을 L, 오른쪽 자식을 R 이라고 하면
A.lcnt = if (L의 왼쪽 수와 R의 왼쪽수가 같다면) L.maxcnt + R.lcnt
else L.lcnt
A.rcnt = if (L의 오른쪽 수와 R의 오른쪽수가 같다면) R.maxcnt + L.rcnt
else R.rcnt
A.maxcnt = max (L.maxcnt, R.maxcnt, A.lcnt, A.rcnt)
if (L의 오른쪽 수와 R의 왼쪽수가 같다면) max (max, L.rcnt + R.lcnt)
 
다른 해법
입력된 값을 같은것끼리 묶어서 1부터 차례로 바꾸어준다.
입력예를 바꾼 예는 다음과 같다.
-1 -1 1 1 1 1 3 10 10 10 -> 1 1 2 2 2 2 3 4 4 4
바뀐 숫자의 개수를 기준으로 트리를 만든다.
범위가 지정되면 해당범위의 왼쪽 값의 개수와 오른쪽 값의 개수, 왼쪽값+1부터 오른쪽값-1 까지의 최대개수 중 최대값을 출력하면 된다.
각각의 개수는 아래 예와 같이 오른쪽부터 누적된 개수와 왼쪽부터 누적된 개수를 구해 놓으면 상수시간에 구할 수 있고 가운데 값들중 최대개수는 log N 만에 구할 수 있다.
 
변환된 입력값 1 1 2 2 2 2 3 4 4 4
왼쪽부터 누적 1 2 1 2 3 4 1 1 2 3
오른쪽부터 누적 2 1 4 3 2 1 1 3 2 1
 
 
레이저 감시장치
 
최소점덮개 찾기(minimun vertex cover) 문제이다.
쾨닉의 정리에 의하면 최소점덮개 = 최대매칭 의 개수와 같으므로
보석이 있는 위치를 기준으로 각 행과 열을 매칭한 후 네트워크 플로우 알고리즘으로 최대매칭의 개수를 구하면 된다.
 
 

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.