2020년 세종과학예술영재학교 정보올림피아드 풀이

※2020/11/23 - [Problem Solving] - 2020년 세종과학예술영재학교 정보올림피아드 후기에서 문제 풀이를 분리한 글입니다.

문제 소개 및 풀이

문제 체감 난이도와 사용 알고리즘은 다음과 같습니다.

문제 난이도 : A < B < D < C 

핵심 알고리즘 : A 누적합 배열, B 투포인터, C 다이내믹 프로그래밍, D 세그먼트 트리

 

문제 A: 할로윈과 별사탕(L)

 

크기 N 배열에서 주어진 위치 k를 제외한 모든 위치에 x를 더하는 쿼리를 M번 처리하는 문제입니다.

모든 쿼리를 처리한 후 최종 배열을 출력해야 합니다.

$ 1<=N,M<=10^5$

 

풀이

N,M의 크기 제한이 크므로 Naive(순진)한 방법으로는 해결할 수 없습니다.

 

원소 업데이트 쿼리가 존재한다면 펜윅트리 혹은 세그먼트 트리를 써야겠지만, 이 문제에서는

차이배열 + 누적합을 사용하는 것으로 충분합니다.

 

주어진 배열을 A[]라 했을 때 d[i] = A[i] - A[i-1]로 정의합시다.

A[0] = 0이라 두면 자연수 i에 대해 $A[i] = \sum_{j=1}^{i}d[i]$가 성립합니다.

이를 통해 A[i], A[i+1], ... , A[N]에 x를 더하는 것은 d[i] += x와 동치임을 알 수 있습니다.

A[s], ... , A[e]에 x를 더하는 것은 A[s], ... , A[N] 에 x를 더하고 A[e+1], ... , A[N] 에 x를 빼는 것과 같으므로 

곧 d[s] += x, d[e+1] -= x와 동치입니다.

 

이 문제에서 주어진 쿼리는 A[1]..A[k-1], A[k+1]...A[N]에 x를 더하는 쿼리이므로 각 쿼리를 $d[1] += x, d[k] -= x, d[k+1] += x$ 3번의 연산으로 처리할 수 있습니다.

 

작년 정올 3번과 비슷한 아이디어입니다.

 

구현 : colorscripter.com/s/PCsq8Mx

문제 B: 기념품 가게

크기 N 배열과 정수 K가 주어집니다.

합이 K인 연속한 구간의 개수를 구하는 것이 문제입니다.

 

풀이

누적합 배열이 단조 증가한다는 사실을 이용해

투포인터 / 이분탐색으로 해결할 수 있습니다.

 

웰노운이고 이 문제와 동일한 문제이므로 먼저 스스로 풀어보시는 것을 추천합니다.

 

주어진 배열이 A[]일 때   S[i] = A[1] + ... + A[i]로 정의합시다.

 

그러면 A[a] + ... + A[b] 는 S[b] - S[a-1] , 두 항의 뺄셈으로 나타낼 수 있습니다.

곧 우리의 문제는 다음과 같이 바뀝니다.

S[b] - S[a] <= K인 (a,b) 순서쌍의 개수를 구하라. (단, a<b) 

 

임의의 b에 대해 이를 만족하는 a의 개수를 어떻게 구할까요?

위 식을 정리하면 S[a] >= S[b] - K가 됩니다.

즉 1<=a= S[b] - K가 되는 a의 개수를 구하면 되겠습니다.

S[]는 단조 증가하는 배열이므로 S[0] = 0 부터 S[b-1]까지 S[b] - K의 lower_bound p를 찾으면 

가능한 a의 개수는 b-p가 됩니다.

 

b를 1부터 n까지 순회하면서 투포인터/이분탐색 등으로 가능한 a의 개수를 구해 ans에 더해주면 됩니다.

 

투포인터 구현 : colorscripter.com/s/E2LE3mq

이분탐색 구현 : colorscripter.com/s/NsnA5JW

문제 C: 정육면체 팔찌(2)

N개의 주사위가 주어집니다. 주사위의 각 면에는 1부터 6까지 숫자가 한 번씩 쓰여 있고 그 배치는 주사위마다 서로 다를 수 있습니다. 

 

주사위로 팔찌를 엮을 건데, 실이 뚫는 주사위의 두 면은 정반대 위치에 있어야 합니다.

편의 상 그 두 면을 팔찌에 있는 순서대로 앞면, 뒷면이라 합시다.

 

팔찌에서 인접한 주사위 간 서로 마주보는 면들의 숫자는 같아야 합니다.

즉, 앞 주사위의 뒷면과 뒤 주사위의 앞면에 쓰여 있는 숫자가 같아야 합니다.

 

N개의 주사위 중 M개 이상의 주사위를 주어진 순서대로 (연속하지 않아도 됩니다) 골라 팔찌를 만들 때 가능한 팔찌의 경우의 수를 구하는 문제입니다. 

 

$1<= M <= N <= 1000$

 

풀이

경우의 수, $N<=1000$  =>  $N^2$ DP 각이 나왔습니다.

천천히 들어가봅시다.

 

모든 경우를 살펴보는 알고리즘을 생각해봅시다.

 

i번째 주사위를 봅니다.

(1) 주사위를 팔찌에 이용합니다. 실을 뚫을 두 면과 방향을 정합니다. 

(2) 주사위를 팔찌에 이용하지 않습니다.

i+1번째 주사위로 넘어갑니다.

 

M개 이상의 주사위를 고르고 첫번째 고른 주사위의 앞면과 마지막으로 고른 주사위

 

이 알고리즘이 맞아보이시나요? 놀랍게도 아닙니다. 1번째로 주사위를 고르고 나면 (1)에서 두 면과 방향이 자동 결정됩니다.

 

예제를 들어 설명 하자면

(a b) : 숫자 a와 숫자 b가 서로 정반대 면에 그려져 있다.

1번째 주사위가 (1 6) (2 4) (3 5) 

2번째 주사위가 (1 6) (2 3) (4 5)라고 합시다.

1번째 주사위에서 (1 6)을 고르고 1을 앞면, 6을 뒷면이라고 하면 

2번째 주사위에서는 무조건 6을 앞면, 1을 뒷면으로 해야 합니다.

 

마찬가지로 1번째 주사위에서 (2 3)을 고르고 2를 앞면, 4을 뒷면이라 하면

2번째 주사위에서는 4를 앞면, 5를 앞면으로 해야 합니다.

 

이처럼 첫 주사위를 결정되면 그 뒤로는 어떤 주사위를 보든 간에 앞면과 뒷면이 결정되어 문제가 훨씬 쉬워집니다.

 

DP 식을 다음과 같이 정의합시다.

 

$dp(i,j,k,w)$ :$1~i$번째 주사위 중 $j$개의 주사위를 골랐을 때 가장 앞면의 숫자가 $k$이고 가장 뒷면의 숫자가 $w$일 경우의 수

 

이때 $k == w$이고 $j>=M$이면 고른 주사위들로 팔찌를 만들 수 있습니다.

 

i번째 주사위에서 w의 정반대에 있는 숫자를 chk(i,w)라 합시다.

i번째 주사위를 고르지 않을 수도 있고, 고를 수도 있습니다. 이를 통해 점화식을 세워 봅시다. 

$dp(i,j,k,w) = dp(i-1,j,k,w) + dp(i-1,j-1,k,chg(i,w)) $

 

$1<=i,j<=N$ , $1<=k,w<=6$ 이고 각 원소를 채우는데 $O(1)$이 걸리므로

총 $O( (6N)^2 )$ 시간복잡도에 모든 dp테이블을 채워주면 됩니다.

 

최종 정답은 $\sum_{i=1,j=1}^{i=N,j=6}dp(n,i,j,j)$입니다.

 

구현 : colorscripter.com/s/P8FBjcD

 

문제 D: 보물 찾기

N,M이 주어질 때 다음과 같은 쿼리를 M개 처리해야 합니다.

쿼리 1 :  A번 학생이 B라는 수를 등록한다.

쿼리 2 : 지금까지 등록된 수 중 K번째로 큰 수를 등록한 학생의 번호를 출력한다.

 

$1<=N,M<=10^5$ , $1<=A<=N$ , $1<=B<=10^9$이고 주어지는 모든 A와 B는 서로 다름이 보장됩니다.

또한 쿼리 2가 들어오기 전까지 K개 이상의 쿼리 1이 들어왔음이 보장됩니다.

 

풀이

쿼리 2가 들어올 때마다 지금까지 들어온 모든 학생의 수를 확인한다면 총 시간복잡도는 $O(NM)$이 되어 Time Limit Exceeded를 받게 됩니다. 

 

고로 모든 쿼리를 $O(N)$ 보다 작은 $O(log n)$ 또는 $O(log^2 N)$에 처리해야 합니다.

 

풀이는 3가지가 있습니다.

 

1. 세그먼트 트리 + 좌표압축

2. 다이내믹 세그먼트 트리 + Map

3. Indexed Set 사용

 

1번에서 3번 풀이로 갈 수록 더 직관적이나, 더 많은 사전 지식이 필요합니다.

 

대회 중에는 1번 풀이를 짜서 정답을 받고, 남은 시간 동안 2번 풀이도 구현해 정답을 받았습니다. 3번 풀이는 ..생각하고 바로 던졌습니다.

 

1) Segment Tree + 좌표압축을 이용한 풀이

$1<=B<=10^5$이라고 가정해봅시다.

$10^5$ 크기 수열을 담는 세그먼트 트리를 하나 만듭니다. ( $ n = 10^5 $ )

1번 쿼리가 들어올 때마다 B번째 칸의 수를 1로 업데이트합니다. ( $O(log n)$ 소요 )

 

2번 쿼리를 $O(log^2 n)$에 수행하는 방법은 다음과 같습니다.

 

sum(x)를 세그먼트 트리에서 1번 ~ x번 원소의 합이라 정의하면

K번째 작은 원소는 sum(x) = k인 최소 x입니다.

sum(x)는 x에 대해 단조 증가합니다. 또한 세그먼트 트리를 이용해 sum(x)를 $O(log n)$에 구할 수 있습니다.

 

고로 x를 $1$부터 $10^5$까지 파라메트릭 서치를 돌려 sum(x) = k인 최소 x를 $O(log^2 n)$에 구하면 됩니다. K번째 큰 원소도 마찬가지로 하여 구할 수 있습니다.

 

그런데 아직 $1<=B<=10^9$인 것은 변함이 없습니다. 범위가 너무 커요!

이를 어떻게 해결할까요?

 

쿼리의 수가 $10^5$개 이하인 것에 주목합시다.

쿼리의 수가 $10^5$ 이하 => 1번 쿼리 $10^5$ 이하 => 수 삽입 $10^5$이하 => 수 종류 $10^5 이하$

즉, 우리에게 주어지는 수의 종류는 어차피 $10^5$ 이하입니다.

K번째 큰 수를 구한다는 것은 수의 대소 관계만 관련이 있다는 것입니다.

즉 우리에게 주어진 $10^5$개의 수들을 대소 관계에 따라 $1~10^5$로 압축해버려도 원래 수들 간 대소 관계는 유지됩니다. 

이런 기법을 좌표 압축이라 부릅니다. 이 글을 참고해주세요.

 

고로 범위를 $10^5$ 이하로 줄일 수 있습니다. 

 

실제 구현에서는 좌표 압축을 먼저 하고 세그먼트 트리를 구현하면 됩니다.

 

여담으로 2번 쿼리를 $O(log n)$에 구현할 수도 있습니다. 

힌트) 세그먼트 트리의 루트에서부터 분기해 나간다.

 

1번 풀이 구현

colorscripter.com/s/sBvya9T

 

2) Dynamic Segment Tree + Map 를 이용한 풀이

 

단도직입적으로 말하면 좌표압축이 필요없습니다.

수 범위가 $1 ~ 10^9$인 세그먼트 트리, 다이내믹 세그먼트 트리를 사용합시다.

다이내믹 세그먼트 트리에 관한 설명은 이 글을 읽어 주시기 바랍니다.

 

여기서는 파라메트릭 서치가 아니라 1번 풀이 마지막에 소개한 $O(log n)$ 방법으로 2번 쿼리를 처리했습니다.

 

삽입한 수에 대응되는 번호를 구해야 하는데, 삽입된 수가 매우 크므로 이는 해싱(unordered_map), 이분탐색(map)을 이용해 처리할 수 있습니다. 

 

2번 풀이 구현

colorscripter.com/s/6KXy1PI

 

3) Ordered Set을 이용한 풀이

C++에서 set은 집합 자료구조입니다.

set의 특징은 첫째로 중복된 데이터가 없는 것이고, 두번째로 정렬되어 있는 것입니다.

set의 강력함은 원소 삽입, 원소 삭제, 이분탐색을 모두 $O(log n)$에 처리할 수 있는데서 나옵니다.

 

이 문제에 set을 이용할 수 있을까요? 

쿼리 1은 (B,A)를 set에 삽입합니다. 이때 크기 비교는 B를 통해 이루어집니다.

쿼리 2는 set에서 K번째 큰 원소를 꺼내 학생 번호를 출력합니다.

 

와! 간단하죠? 모든 쿼리는 $O(log n)$ 에 이루어질

것 만 같았습니다.. But, 어림도 없습니다.

 

쿼리 1은 자명합니다. 그러나 쿼리 2는 안타깝게도 이루어지지 못합니다. set은 인덱스를 지원하지 않기 때문입니다. i번째 원소를 구하지도, 어떤 원소가 몇번째 원소인지도 알지 못합니다.

 

하지만! 훌륭한 정보과학자들이 이미 레드블랙트리를 이용해 인덱스 있는 set을 만들어 놓았습니다.

 

와 이제 갖다 쓰기만 하면 되겠네요?

네 맞습니다! 아래 코드를 외워서 대회장에서 자유롭게 꺼내들 자신이 있다면 말이죠.

이 코드를 외우고 있다면 당신은 분명 범상치 않은 사람입니다.

이제 이 자료구조를 이용해 쉽고 간단하게 문제를 풀면 됩니다.

 

자세한 사용법은 이 글을 참고하세요.

 

대회 중 구현하지 않았습니다. 쉽고 간단하니 추후 채점이 가능해지면 구현해보길 추천합니다.

 

 

C번이 가장 재미있었습니다.