6월 ~ 7월 1주차 PS 정리

결국 1학기가 종강하고 나서야 PS를 다시 조금씩 시작했다. :( 

앞으로 이렇게 묶어서 포스팅할때는 코드를 Github을 이용해서 올리려고 한다.

 

BOJ 16440, 경북대학교 Goricon 2018, "제이크와 케이크"

난이도 : Solved AC Platinum 5

s와 k가 나열된 문자열을 최소 개수의 연속된 조각으로 자르고, 이를 재배열하여, 양쪽이 같은 개수의 s와 k를 가질 수 있게 하는 문제이다. 

답이 2 이하라는, 즉 2번의 커팅으로 문제를 반드시 해결할 수 있다는 놀라운 Claim을 증명하려고 한다. 이는 다시 말해, 하나의 $n/2$짜리 연속한 segment가 $s$와 $k$를 동수로 포함하도록 자를 수 있음을 의미한다.

$n/2$ 개 짜리 연속된 구간을 먼저 잡고, 이를 오른쪽으로 살짝 한칸씩 민다고 생각하자. 이때 $s$의 개수는 많아야 한 개가 바뀌기 때문에, 반드시 어떤 지점에서는 $s$를 $n/4$ 개 포함하는 구간이어야만 한다. 만약 모든 지점에서 $s$의 개수가 절반 이하라면 전체에서 $s$의 개수가 절반이 될 수 없기 때문이다.

즉, 답이 1인지 판정하고 (가운데를 한번 잘라서 되는지 보고), 답이 2임을 확신하며 위 '구간 밀기' 를 코드로 구현하면 끝나게 된다. 부분합을 이용하면 매우 간단한다.

여담으로, 이 문제는 위상수학의 놀라운 정리인, (3B1B에도 소개된) Borsuk - Ulam Theorem 을 이용하면 일반화할 수 있다. 3B1B 비디오는 정확히 이와 같은 문제를 소개하며 시작하고 있다. 위상수학 1만 들었기 때문에 이 정리에 대해서는 잘 모르지만 3B1B는 한번쯤 볼만한것 같다. (링크) 간단하게 얘기하자면, $S^n \to \R^n$ 연속함수에 대해 반드시 $^\exists x \in S^n$, $f(-x) = f(x)$ 라는 정리인데, 이 정리를 이용하여 $n$종류의 물건으로 일반화한 ($n$번의 커팅으로 가능하다는) 위 문제의 강화된 버전이 해결 가능하다. 

코드 : [링크]

 

BOJ 13561, ICPC Dajeon Regional 2016 C, "House Rental"

난이도 : Solved AC Platinum 5

문제를 잘 읽고 정리하면, 결국은 $k$종류의 시설물을 합하여 $n$개가 일직선상에 주어지고, 최소 길이의 구간 (선분) 으로 $k$종류의 시설물을 적어도 한개씩 덮는 문제이다. 뭔가 셋업이 약간 다르지만 최종적인 목표는 2020 카카오 인턴십 코딩테스트 문제 '보석 쇼핑'과 비슷하다.

이러한 문제를 투 포인터 알고리즘으로 해결할 수 있다. 지금 구간에서 이 유형의 시설물 몇개를 봤는지를 관리하는 배열을 이용하여, 일단 오른쪽으로 구간을 늘리다가, 모든 시설물을 확인하였으면 구간의 왼쪽 끝을 당겨서 줄이면서 최소 구간을 찾으면 된다.

코드 : [링크]

 

BOJ 10019, USACO 2014 March Gold II, "Sabotage"

난이도 : Solved AC Platinum 3

별도 포스팅.

 

BOJ 16915 호텔 관리

난이도 : Solved AC Platinum 3

$m$개의 스위치와 $n$개의 방이 주어지고, 한 방은 두개의 스위치에 연결되어 있다. 이때 스위치는 그 스위치에 연결된 모든 방의 전원 상태를 바꾼다 (켜진 방을 끄고, 꺼진 방을 켠다). 이때, 스위치를 잘 적절히 조작해서 모든 방의 전원을 켜고 싶다. 

켜져 있는 방을 내버려 두기 위해서는, 그 방에 연결된 스위치 두개가 다 0이거나 1이어야 한다.

꺼져 있는 방을 켜기 위해서는, 둘 중 하나만 1이어야 한다.

2-SAT 문제를 생각하면 된다. 각각의 스위치 상태를 2SAT의 원소 (boolean variable)로 생각하자. 켜져 있는 방을 내버려 두기 위해서는 $(a \lor \lnot b) \land (\lnot a \lor b)$ 가 만족되어야 한다. 꺼진 방을 켜기 위해서는 $(a \lor b) \land (\lnot a \lor \lnot b)$ 가 만족되어야 한다. 즉 모든 방에 대해 2개씩의 2SAT-Clause를 추가하여 스위치가 만족해야 할 논리식을 찾을 수 있고, 이를 풀면 된다.

dlwocks31과 연습에서 풀었던 문제인데 $n$과 $m$을 반대로 보고 6번의 Runtime Error를 받았다. :(

코드 : [링크]

 

BOJ 17353, 선린 제 3회 천하제일 코딩대회 E, "하늘에서 떨어지는 1, 2, ... R-L+1개의 별"

난이도 : Solved AC Platinum 2

문제를 해석하면 결국은 어떤 구간에 어떤 일차함수를 더하는 쿼리와, 점 $x$에서 그 더해진 일차함수의 총합을 Evaluate하는 쿼리를 처리하는 문제이다. 일차함수를 직접 관리하는 대신, 일차함수의 기울기와 y절편을 나누어 관리하자. 일차함수의 기울기를 관리하는 Segment Tree와 y절편을 관리하는 Segment Tree를 만들어서, 각각에 Lazy Propagation을 이용하여 값을 더하면 된다. 

코드 : [링크]