7월 1주차 모의고사 결과 및 문제풀이 > 공지게시판



정올소식

커뮤니티

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

7월 1주차 모의고사 결과 및 문제풀이

페이지 정보

작성자 kimdongkyoo 작성일18-07-11 18:59 조회519회 댓글0건

본문

수상자

 

초등부 - 이승준

중등부 - 이동현

고등부 - 호수리

 

문제풀이

#A. 수학 올림피아드

루프를 돌리면서 수학 성적이 90점이 넘는 경우에만 수학 성적을 합하고, 동시에 90점이 넘는 사람의 수를 센다. 합을 사람 수로 나누면 평균값이므로, 그것을 구하면 답이다. 소수점 둘째 자리자리 반올림하는 것을 할 줄 알도록 하자. (%.2f)

 

 

#B #A. 만화책

입력 받은 배열과, 같은 배열을 하나 더 만들어서, 복사본은 정렬해 놓는다.

정렬한 배열과 원본 배열을 비교한다.

두 배열이 완전히 같은 배열이면 AWESOME을 출력한다.

두 배열이 두 곳에서만 다르면, GOOD 을 출력한다.

그 외의 경우에는, OH NO를 출력한다.

#C #B #A. 그뤠잇 넘버

문제에서 하라는 대로 단계를 밟아나가기만 하면 되는 문제이다.

xf(x)를 계속 적용시켜나가다 1이 나온다면, 그뤠잇 넘버이다.

자기 자신이 나온다면 스튜핏 넘버이다.

x10^18 이하로, 숫자가 매우 커보이나,

가장 최고의 수인 99,999,999,999,999,999를 고려해서

f(99,999,999,999,999,999)를 해 보면, 9^2 +9^2 + … 9^2 17번 더하는 것이므로, 9^2 * 17 = 1377밖에 되지 않는다. 따라서 시간에 대해 걱정할 필요가 전혀 없다.

#D #C 광자포 건설

문제가 주구절절 잡다한 것들이 써 있지만, 직관적으로 말해서, 오목한 부분, 즉 움푹 패인 부분을 매우면 되는 문제. 이를 조금 구체적으로 말하자면, 어떤 정해진 x값에 대해서, y값의 최대값과 최소값 사이에는 항상 광자포가 건설 되어 있어야 하고, 어떤 정해진 y값에 대해서, x값의 최대값과 최소값 사이에는 항상 광자포가 건설 되어 있어야 한다는 뜻이다. 그런데, x를 좌에서 우로 움직이면서 추가해야하는 광자포 수를 세고, y를 밑에서 위로 움직이면서 추가해야하는 광자포 수를 세면, 좌우로 움직이면서 센 광자포와 상하로 움직이면서 센 광자포 중에 겹치는 것이 생긴다. 이 겹치는 것을 세기가 난해하므로, 이 방법은 WA판정을 받는다. 어느 한 좌표를 기준으로만 생각하는 방법이 필요하다.

5ac0e65b9ed0b8cffbc782776465fb00_1531302
x값만 왼쪽에서 오른쪽으로 순회하는 방법을 생각해 보자.

전체 y값의 최대값을 yMax, 최소값을 yMin이라고 하자.

 

x값 별로, x가 왼쪽부터 yMin이 위치한 x값까지 움직일때는, y값의 하한선이 하향해야 한다.

마찬가지로, x값이 오른쪽부터 움직일 때 역시 y값의 하한선이 하향해야 한다.

마찬가지로 x가 왼쪽부터 yMax가 위치한 x값까지 움직일때는 x값의 상한선이 상향해야 한다.

오른쪽부터도 마찬가지다.

5ac0e65b9ed0b8cffbc782776465fb00_1531302

x값별로 구한 상한선에서 하한선까지 뺀 걸 다 더한게 최종 광자포 수이다.

여기다가 원래 있었던 광자포(그림의 하얀 광자포 수)를 빼면, (노란 광자포 수)이 나온다.

 

 

#D #B 쉼표

명제관계에서 aób이고 bóc이면 aóc이라는 상관관계가 다수 엮여 있을 때, 그래프를 이용한다. 이 문제 역시 상관관계가 엮여있으므로, 그래프 문제라는 일감을 가지고 출발한다.

우리가 쉼표를 찍는 곳은 단어의 뒤 아니면 단어의 앞이므로, 각 단어마다 앞과 뒤를 상징하는 노드를 하나씩 만들어서 그래프를 그린다. 그래프는 단어 a의 뒤에 단어 b의 앞이 있다면 간선으로 연결하는 식으로 구현할 수 있다.

만약 어떤 단어의 앞에 쉼표가 있다면, 그 노드에 연결된 모든 요소들은 다 쉼표가 있는 것이다.

예제를 통해 설명 해보자면,

go run program. run program, run. program better and better.

better의 앞óprogram의 뒤órun의 앞ógo의 뒤. 이 중 하나라도 쉼표가 있다면, 다 쉼표를 찍어야 한다. 따라서 program의 뒤에서 dfs를 이용하여 연결된 노드들을 다 체크한다. 위의 정점들은 다 쉼표가 찍히는 위치들이 된다. 답을 찾기 위해선, 앞에서부터 돌면서 체크된 곳에 쉼표만 추가해주면 된다.

STL string이나 map의 사용법을 모른다면, 구현이 상당히 힘들어질 수도 있다.

#C. 무선 통신

문제를 잘 읽어보면, 이것이 강한 연결 요소(Strongly Connected Component, SCC)를 찾는 문제임을 알 수 있다. AàB로 전송 가능하고, BàA로 전송 가능하다는 것은, 방향 그래프에서 A에서 B로 가는 경로가 있고, B에서 A로 가는 경로가 있으면 강한 연결 요소라는 정의와 정확히 일치하기 때문이다.

강한 연결 요소를 찾는 알고리즘인 코사라주 알고리즘은 O(V+E)으로, 선형 시간복잡도이다. 우리에게 주어진 n200,000 이하로, 시간이 충분해 보인다. 문제는 그래프가 직접적으로 주어진 것이 아니기 때문에, 가장 순진한 방법으로 그래프 전체를 구성해서 프로그래밍하면(, 모든 i,j 쌍에 전송 가능/불가능을 따져 간선을 그리는 방법을 사용한다면), 모든 i, j쌍을 순회하게 되므로 O(n^2)이 된다.

이를 어떻게 줄여나가야 할까? 코사라주 알고리즘 자체에는 문제가 없다. 이 알고리즘은 언제나 그렇듯 선형시간안에 돌아간다. 문제는, 그래프를 직접 구성할 시간이 없다는 것이다. 따라서, 코사라주 알고리즘의 dfs순회 중에 간선을 O(n)보다 빠른 시간에 찾아내는 것이 우리의 목적이 된다.

문제에 주어진 식을 다시 한번 살펴보자.

|i-j|<=a[i]+b[j] 면 전송 가능.

이를 조금 전개하면,

i-a[i]<=j+b[j] (if, i >= j)

i+a[i]>=j-b[j] (if, i<j)

가 된다. 다행히도! i-a[i], j+b[j], i+a[i]j-b[j]등의 값들은 입력된 후 절대 바뀌지 않는 변수들이다. , 다시 코사라주의 알고리즘의 dfs 순회로 돌아가자.

함수 dfs(i) 내에서, i번째 도시를 순회중일 때, i와 연결된 도시 j를 찾는 방법은, 위 식에 따라서 다음과 같다.

구간 [1,i)에서 i-a[i]보다 큰 j+b[j]가 있을 때 j로 이동 가능, 또는

구간 (i,N]에서 i+a[i]보다 작은 j-b[j]가 있을 때, j로 이동 가능

구간에서 큰”, “구간에서 작은”. 맞다. 세그먼트 트리(인덱스 트리, 문제 푸는 여러분이 뭐라고 배웠든간에)의 기본 아이디어이다. j+b[j]값이 저장된 max_segment treej-b[j]값이 저장된 min_segment tree만 있다면, 구간에서 이동할 수 있는 노드가 있나 없나, 있다면 어느 노드인가를 O(log(n))만에 찾을 수 있게 된 것이다. 한번 이동할 때마다, dfs(i)내에서 다음 이동 노드를 찾기 전에, 자기 자신을 구간트리에서 제외시켜버리면(이 제외시키는데도 log(n)의 시간이 든다, 세그먼트 트리니깐), 한번 순회한 i로 다시 돌아올 일도 없다. 이렇게 코사라주 알고리즘의 dfs순회를 안전하게 할 수 있다.

코사라주 알고리즘 내에는 모든 간선을 역방향으로 놓고, dfs를 한번 더 돌리는 과정이 있다. 이는 i보다 작은 구간에서 min_segment tree를 쓰고, i보다 큰 구간에서 max_segment tree를 쓰면 간단하다. 결국 자기한테 전송할 수 있는 노드를 찾는 것이 역방향 간선이기 때문이다.

#D. 네 명의 왕자

(우리가 늘 풀어왔던 여느 경우의 수 문제들 처럼,) DP로 접근한다. 아주 담백하고 솔직하게, 하던 대로 접근해 보자.

DP[i][j]i번째 부대까지 봤을 때, j개의 부대를 전투에 참여시키는 경우의 수라고 하자. (이하 모든 설명에서 MOD 107은 생략되어 있다.)

DP[i][j]는 정의에 따라 (i번째 부대를 사용하지 않는 경우인) DP[i-1][j] + (i번째 부대를 사용하는 경우인)DP[i-1][j-1] * (i번 부대를 왕의 분대와 왕자의 분대로 나누는 경우)가 된다. 늘 하던 그 DP 풀이이다. 여기까지 하고 나면, 어려운 부분은 i번 부대를 왕의 분대와 왕자의 분대로 나누는 경우를 찾는 문제이다.

이는 i번 부대원이 a[i]명이라 할 때,

a[i] C 0+a[i] C 4+a[i] C 8 + …+a[i] C 4p(p 4p<=a[i]인 가장 큰 p, p는 양의 정수)가 된다.

이를 for문으로 단순 반복해서 구하면, 부분점수인 30%을 챙겨갈 수 있다.

저 식을 구하기 위해서, 수식을 이용한다.

(x+1)^n의 전개식에서, 다음을 알 수 있다.

n C 0 + n C 1 + n C 2 + … + n C n = 2^n (x=1대입)

n C 0 – n C 1 + n C 2 - … ± n C n = 0 (x=-1대입)

두 식을 더하면, n C 0 + n C 2 + … + n C 2p = 2^(n-1)

또한, x에 복소수 i–i를 대입하여 더하면, (여기서 ii^2=-1이 되는 허수이다.)

n C 0 – n C 2 + n C 4 - … ± n C 2p 를 구할 수 있고,

최종적으로 구한 두 식을 더해서

n C 0 + n C 4 + n C 8 + … + n C 4p를 구할 수 있다. n 대신 a[i]를 넣기만 하면 우리의 승리이다.

모든 식이 제곱식으로 표현되므로, log(a[i])만에 구할 수 있으며

따라서 우리가 원래 풀려던 DP풀이는 O(nklog(a[i]))만에 구할 수 있다.

 


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.