12-23 Merry problem solving!

2018 merry problem solving!

12-23 : Day3

boj 슬랙에서 koosaga님이 진행하시는 2018년 연말 merry problem solving 스터디(앳코더 문제들 매일 목표 정해놓고 풀기)에서 푼 문제에 대한 정리글. 풀이는 내가 풀기 쉬웠던 문제부터 어려웠던 문제까지 순서대로 나열되어 있다.

APC 1C. Vacant Seat (500pts)

N개의 자리(N은 홀수)로 이루어진 원탁이 있다. 남녀가 앉는데 서로 같은 성별은 붙어 앉을 수 없다. N은 홀수기 때문에 반드시 빈 자리가 생기고, 현재 원탁의 자리 상태는 알 수 없다. 인터랙티브하게 쿼리를 날려서 i번째 위치에 남자가 앉아 있는지 여자가 앉아 있는지 혹은 비어 있는지 확인할 수 있는데, 20번 아래로 쿼리를 날려서 빈 자리가 있는 위치를 찾자.

풀이

이분 탐색으로 찾을 수 있다. 원탁의 0번째 위치 성별을 k라고 하자. 그러면 만약 2x 위치 자리 성별 역시 k인 경우, 2x+1 ~ n-1 자리까지에 반드시 빈 자리가 하나는 있어야 한다. 왜냐하면, 2x ~ n -1까지 남는 자리 개수가 홀수기 때문에 빈자리 없이 채워넣을 경우 반드시 n-1번째 자리와 0번째 자리의 성별이 같아지기 때문이다. 따라서 이 경우 2x + 1 ~ n-1 번째 구간만 확인하면 된다.

반대로, 2x 위치 자리의 성별이 k가 아닌 경우는 0 ~ 2x -1 위치의 자리 중에 하나는 빈 자리가 있어야만 한다. 빈 자리 없이 순서대로 채워넣을 경우 반드시 2x번째 위치와 0번째 위치는 서로 같은 성별이 되어야만 하기 때문이다.

따라서 위 두 가지 성질을 가지고 이분탐색을 반복하면 자리 개수 제한이 10만이므로, log2(10만) = 17번 정도에 맨 처음 0번째 자리 성별을 확인하기 위한 쿼리 1번을 포함해서 18번 정도의 쿼리면 반드시 빈 자리가 있는 위치를 찾을 수 있게 된다.

ARC 100D. Equal Cut (600pts)

길이 N짜리 배열 A가 있다. 이 배열을 4개의 연속된 구간 B,C,D,E로 나누려고 한다. 나누는 위치는 자유롭게 정할 수 있지만, B,C,D,E 각각의 연속한 구간의 원소들 합을 P,Q,R,S라고 했을 때 이 4가지 값의 최댓값과 최솟값의 차이를 가능한 한 적게 만들어야 한다. 이 때 P,Q,R,S의 최댓값과 최솟값의 차이를 구하여라.

풀이

배열을 4개의 구간으로 자르는 각각의 위치를 맨 앞에서부터 순서대로 x,y,z라고 하자(x < y < z). 이 때, y 위치를 고정해놓고 생각하면 x와 z 위치를 정하는게 비교적 간단해진다. y를 기준으로 분할한 배열의 왼쪽을 L, 오른쪽을 R이라고 하자.

이제 L도 두 부분으로 나누고 R도 두 부분으로 나누되 나뉜 네 부분의 합 차이가 최소가 되게 만들어야 한다. 이 때 L, R을 서로 독립적으로 생각하고 L에서 나눈 두 부분의 합의 차이를 최소로, R에서 나눈 두 부분의 합의 차이를 최소로 각각 만들어줘도 전체 4개 합의 차이가 최소가 된다.

왜냐하면, 전체 4개 합의 차이 최소는 식으로 나타내면 max(P,Q,R,S) - min(P,Q,R,S)인데, 이를 분할해서 생각하면 max(max(P,Q), max(R,S)) - min(min(P,Q), min(R,S))로 볼 수 있다.

여기서 L을 두 개의 부분 P,Q로 나누되 이 두 부분의 합의 차이를 최소로 한다는 건 max(P,Q) - min(P,Q)가 최소가 되게 P와 Q를 설정한다는 뜻이다. 그림으로 그려보면 이해하기 쉬운데, 결국 양쪽 각각의 구간을 최대한 좁게 만들면 그 양쪽 구간의 합 구간 역시도 최대한 좁아지게 되기 때문에 전체 값이 최소가 된다.

그러면 이제 고정된 y에 대해서 왼쪽 오른쪽을 분리해서 x와 z가 가야하는 위치를 찾을 수 있는데, 이러한 위치는 부분합 배열에서 이분탐색을 이용하면 O(logN)에 찾을 수 있다. 모든 y좌표에 대해 수행해주면 O(NlogN)에 해결 가능. 

혹은, y = 2 ... N - 1까지 이동하고, 이 때 x = 1부터, z = 3부터 시작해서 조건을 만족할 때까지 포인터를 옮겨가며 계산하면 O(N)에 해결 가능하다. 

y가 오른쪽으로 이동할 때마다 1..x 합은 고정인데 x+1..y는 증가하고, 반대로 y오른편에서는 y+1..z는 감소하는데 z+1..n은 그대로기 때문에 y가 이동할 때마다 x 포인터와 z포인터는 항상 증가하는 방향으로 움직이게 되기 때문이다.

CODE FESTIVAL 2017 Final C. Time Gap (500pts)

N+1개의 도시가 있다. 타카하시는 자기 도시의 로컬 타임 0을 기준으로 다른 N개 도시와의 시차를 기록해뒀다. 도시별 시간 차이는 해당 도시의 시간이 d일 때 min(d, 24 - d)로 정의된다.

이 때, 이 도시별 시간 차이 조건을 만족하는 실제 도시의 로컬 타임 시간은 여러 가지 경우가 있을 수 있는데, 이 때 각 경우에 모든 도시 쌍간의 시차중 가장 값이 작은 것을 s라고 하자. s의 가능한 최댓값을 구하여라. N <= 50, 0 <= D <= 12

풀이

가장 간단하게 접근하면 N개의 도시 각각에 대해 가능한 모든 경우를 만들어보고, 각 경우에 s값을 모두 계산해서 그 중 최대를 출력하면 된다. 이렇게 할경우 시간 복잡도는 O(2^N * N^2)가 된다.

여기서 조금 더 생각해보면, s 값을 구할 때 N^2개의 쌍을 일일히 순회할 필요가 없다. 어차피 시간 값은 항상 0이상 24 미만이기 때문에, c[i] = 시간이 i인 도시의 개수 로 정의하고 c[i] 배열을 채워넣으면 이 배열을 한 번 순회하는 걸로 답을 구할 수 있다. 따라서 이렇게 개선하면 O(2^N * N) 시간에 답을 구할 수 있다.

다시 조금 더 개선해보자. 위에서 c[i] 배열 값이 2이상인 위치 i가 존재할 경우, 그 케이스의 s 값은 0이 될 수 밖에 없다(시간이 서로 같은 도시가 2개 이상 존재한다는 의미이므로). 따라서 이러한 경우는 고려할 필요가 없다. 

그러면 모든 c[i] = 1 혹은 c[i] = 0이라고 생각하면, s배열을 24개의 비트를 가진 정수값으로 생각할 수 있다. 결국, 가능한 c 배열의 경우의 수는 최대 2^24가지가 된다는 뜻이다.

그러면 2^24가지 c 배열이 될 수 있는 모든 케이스에 대해 n개의 도시를 순회하며 그런 케이스를 만들 수 있는지 확인하고 이 때 s 값을 계산해서 갱신하는 풀이를 생각할 수 있다. 이 경우 시간 복잡도는 O(2^24 * N) 정도가 되는데, 약간 애매하다. N=50이고 2^24는 1600만 정도라 2초안에 돈다는 보장이 없다. 오히려 충분히 TLE가 날만한 제한이다.

여기서 어떻게 하면 더 개선할 수 있을까? 전체 경우의 수를 모두 만들어서 그게 가능한지 따져보는게 아니라 애초에 가능한 c값만 모두 생성해보는 방법으로 접근하면 시간복잡도를 더 줄일 수 있다. 문제에서 주어진 입력값 d는 모두 시차 값이라 12 이하의 수인데, 이 d값에 따라 타카하시가 있는 도시의 시간이 0이라고 했을 때 해당 도시가 가질 수 있는 시간은 d 혹은 24 -d 로 정해진다. 

따라서, 각 d값별로 그 d값이 나온 횟수만 계산해두면 이걸 기반으로 나타날 수 있는 도시 시간 배열을 빠르게 계산할 수 있다. 만약 d = 0인 값이 1개라도 있다면 그 경우 항상 s=0이다(타카하시네 도시와 시차가 0이 될 수 밖에 없으므로). 또, d=12인 값이 2개 이상이면 이 경우도 항상 s = 0이다. 마찬가지 원리로, 0 < d < 12 인 d 값에 대해 그 d 값이 나온 횟수가 3번 이상이라면 s = 0이 될 수 밖에 없다. 따라서 이런 경우는 모두 0을 출력하고 끝낸다.

그 외의 경우에는 모든 0..12까지의 d 값에 대해 그 d값이 나온 횟수에 따라 가능한 c배열을 생성하면 된다.

1. d = 0인 경우 => 타카하시네 도시 하나만 있기 때문에 c[0] = 1로 항상 체크 된다.

2. 0 < d < 12인 경우 => d가 나온 횟수가 한 번이면 c[d] 혹은 c[24-d] 둘 중 하나의 값을 1로 체크할 수 있다. 두 경우를 모두 고려해준다. d가 나온 횟수가 두 번이면 c[d] 와 c[24-d]를 모두 1로 체크해줘야 한다(그 외의 경우는 항상 s=0이 되어버리므로)

3. d = 12인 경우 => d가 나온 횟수가 한 번이면 c[d] = 1로 체크한다.

이 때 2번 경우에 의해서만 경우의 수가 2배로 늘어나고 나머지는 경우의 수가 그대로 유지 된다. d 값은 0부터 12까지 총 13가지 값만 가질 수 있기 때문에 가능한 c 배열 경우의 수는 2^13가지를 넘지 않는다는 것을 알 수 있다.

따라서 이렇게 생성한 가능한 모든 c 배열에 대해 모두 s값을 계산하면 O(N + 2^13*24) 정도 시간 복잡도에 답을 구할 수 있음을 알 수 있다.

ARC 97E. Sorted And Sorted (600pts)

2N개의 공이 있다. N개는 흰색 N개는 검은색이다. N개의 흰색 공에 각각 1~N까지 숫자가 중복 없이 적혀 있고 검은 색 공도 마찬가지로 1~N까지 숫자가 중복 없이 적혀 있다. 이 공들은 일렬로 나열되어 있는데, i<j인 i번째 공과 j번째 공에 대해 두 공이 서로 같은 색이면 두 공에 적힌 수 x와 y에 대해서도 x < y가 되게 하고 싶다(즉, 색깔별로 1..N이 정렬된 상태가 되게 하고 싶다).

서로 인접한 공끼리 위치를 바꾸는 연산을 최소 몇 번 수행해야 이렇게 정렬된 상태로 만들어 줄 수 있을까?

풀이

인접한 공끼리 위치를 바꾸는 연산을 k번 수행하면, 나머지 공들의 위치 관계를 바꾸지 않은 채 i번째 공을 i+k번째에 오게 만들어 줄 수 있다(위치 바꾸는 연산을 반복적으로 수행하는 형태를 생각해보면 쉽게 이해할 수 있을 것이다). 이 때 전체 2n개의 배열에서 맨 끝에 오는 공이 무엇일지 생각해보자. 맨 끝에 오는 공은 N이 써진 흰색 공 혹은 N이 써진 검은색 공 둘 중 하나여야만 한다. 따라서 이 두 개의 공 중 하나를 맨 끝으로 보내 놓고 나면, 그 다음은 다시 2N - 1개의 공에 대해 똑같은 작업을 반복하는 형태가 된다.

즉, 모든 경우에 대한 최솟값을 DP로 계산할 수 있다. 식은 다음과 같은 형태가 될 것이다.

DP(w,b) = 1~w까지 적힌 흰색 공과 1~b까지 적힌 흰색 공이 있을 때 전체 정렬을 위해 필요한 최소 연산 횟수

여기서 move(k) = 공 k를 배열의 맨 끝으로 보내기 위해 필요한 연산 횟수 라고 정의하면,

DP(w,b) = min(DP(w-1, b) + move(w), DP(w, b-1) + move(b))

로 정의할 수 있다(제일 큰 두 개의 수 중 하나를 배열의 맨 끝에 보내야 하므로). 이제 move만 구현하면 문제를 풀 수 있다.

흰색 공이 1~w, 검은색 공이 1~b만 남아있는 경우에서 k가 적힌 흰색 공을 맨 끝으로 보내기 위한 횟수 move(k)를 기준으로 생각해보자.

 흰색공 w+1~n, 검은색 공 b+1~n까지는 이미 사용된 상태(현재 배열보다 더 오른쪽에 배치된 상태) 이므로 지금 상태에 영향을 끼치지 않고, 이 공들을 옮기는 과정에서 이 공들을 제외한 나머지 공들의 배치 상태는 바뀌지 않는다. 즉, move(k)는 처음 주어진 공 배열에서 k가 적힌 흰색 공이 있는 위치를 기준으로, 그 공보다 오른쪽에 있는 1~w-1이 적힌 흰색 공의 개수와 1~b-1이 적힌 검은색 공의 개수를 더한 값이 된다. 이 공들은 아직 정렬되지 않은 상태니 배열에 남아 있는 상황이고, w는 옮길 공이니 제외, w+1~n까지 공은 이미 사용된 공이니 고려 대상이 아니기 때문이다.

이러한 공의 개수는 구간 합을 계산하는 자료구조를 이용하면 O(logn)에 구할 수 있고 나는 각 위치별로 자신보다 더 뒤쪽에 있는 공의 숫자 구간별 개수 합을 관리하는 펜윅트리 배열을 만들어서 풀었다. 펜윅트리 초기화 하는 부분에서 O(N^2logN), DP 계산하는 부분에서도 O(N^2logN)의 시간이 걸려서 총 시간 복잡도 O(N^2logN)에 해결할 수 있다.

좀 더 잘 생각하면 이런 자료구조를 쓰지 않고도 O(N^2) DP로 풀 수 있는 방법이 있는 것 같은데 O(N^2logN)으로도 통과하는데에는 무리가 없어서 그냥 이렇게 풀고 넘어갔다.

ARC 99D. Snuke Numbers (500pts)

S(x) = x를 구성하는 모든 자리수의 합으로 정의한다(ex - S(123) = 1 + 2 + 3 = 6). 이 때, 다음 조건을 만족하는 양의 정수 n을 Snuke number라고 부른다.

- m > n 인 양의 정수 m에 대해, 이다.

이 때 k가 주어지면 가장 작은 k개의 snuke number를 출력하라. k번째 snuke number <= 10^15 임이 보장된다.

풀이

못 풀어서 결국 답을 봤다. 답을 안 봤으면 아마 못 풀었을 것 같다.

일단 모든 s(n)에 대해 n/s(n)이 최소가 되는 n 값은 쉽게 찾을 수 있다. 이 n값은 각 s(n) 값에 대해 순서대로 1,2,3,... ,9, 19, 29, 39, ... , 99, 199, 299, ... , 999 ... 순이 되는데 이에 대한 증명은 쉽게 할 수 있다. 맨 끝이 9로 연속되는 숫자가 아닌 경우 앞의 값을 깎고 그 값만큼 뒤의 값을 증가시켜서 9로 만들어주면 s(n)값은 유지되는데 n값은 감소되어서 n/s(n)을 더 작게 만들어줄 수 있기 때문이다.

이 케이스들은 snuke number인게 확실하고, 나머지 snuke number가 되는 케이스를 찾아야 하는데 이 부분에서 온갖 풀이들을 고민해봤지만 결국 실패했다. 이 부분은 앳코더의 에디토리얼을 내가 이해한 내용대로 옮겨 본다. 어떻게 해야 이런 발상을 떠올릴 수 있을지 모르겠다.

f(n) = n이상의 숫자중 가장 작은 snuke number 라고 하자.

내가 찾은 가장 큰 snuke number를 n이라고 하면, 그 다음 snuke number는 f(n+1)이 된다. 따라서 n = 1 부터 시작해서 k번 n = f(n+1)을 반복하면 제일 작은 k개의 snuke number를 찾을 수 있다.

이제 f(n)만 구현하면 된다. f(n)은 다음 snuke number가 될 수 있는 수의 후보를 추린 다음 그 후보들 중에서 n/s(n)이 가장 작은 값을 선택하는 방식으로 구현할 것이다. 이를 위해 아래 명제를 증명한다.

- snuke number는 무조건 맨 끝 d자리가 9로 끝난다.

이를 증명하면 n과 자릿수가 같은 수 중에서 맨 끝 d자리가 9인 모든 경우를 확인해보면 된다(d자리수 999...999 가 snuke number인 것은 확실하기 때문에(맨 처음 이야기한 n/s(n)이 최소가 되는 n값에 해당) 항상 d자리 수의 snuke number가 하나는 존재하므로 같은 d자릿수만 확인해보면 된다.

이제 이 명제를 증명해보자. n이상의 가장 값이 작은 snuke number k의 끝 d-1자리 중에 9가 아닌 수가 섞여있다고 가정하자. 

그러면 d번째 자리의 값을 깎고 뒤쪽 d-1자리 중 9가 아닌 수를 9로 바꿔주면, k는 감소하고 s(k)은 증가하므로, 기존 숫자가 n 이상의 가장 작은 snuke number라는 가정에 위배된다. 따라서 n 이상의 가장 값이 작은 snuke number는 항상 맨 끝 d자리가 9로 끝나야 된다. 따라서 n과 자릿수가 같으면서 n이상인 맨 끝 d자리가 9로 끝나는 수들을 모두 만든 다음 그 중 n/s(n)이 가장 작은 것을 골라주면 된다.