백준 출제한 문제 풀이 요약

너무 오랫동안 여길 방치한 것 같고, 풀이를 올리지 않은 문제도 있길래 각 문제당 간단한 풀이 요약을 올린다.

 

15352 욱제와 그의 팬들

연속된 같은 팬클럽인 사람을 Union-Find로 관리하자. 한명이 빠지면 그 구간의 크기가 1 감소하고, 구간의 길이가 1이였으면 양옆의 구간이 합쳐질 수 있다.

 

15560 15561 구간 합 최대?

흔히 금광 세그라고 불리는 구간합 최댓값 세그먼트 트리를 사용하면 된다. 왼쪽 부분합의 최댓값, 오른쪽 부분합의 최댓값, 구간합의 최댓값, 구간의 합을 노드에 저장하면 잘 합쳐진다.

 

15562 네트워크

각 정점에서 출발하는 경로의 개수를 생각하면 답의 하한은 쉽게 추측할 수 있다. 직관적으로 충분할 것이라 예상할 수 있고, 실제로 그렇다. 나에게로 오는 간선은 위상정렬 상에서 내 앞에서 온다는 점을 생각하면 항상 들어가는 경로 개수가 부족할 일이 없게 할 수 있단 것을 알 수 있다.

 

15563 15564 Äventyr

대회 당시 멍청한 내가 의도한 풀이는 HLD였고, 실제로는 센트로이드 트리를 이용해서 푸는 것이 대중적인 풀이로 보인다. 두 풀이 모두 D(u)를 u가 루트인 서브트리에서 u에서 바이올린으로 가는 최소 거리라고 정의한 후, 트리를 타고 올라가면서 dist(u,v)+D(u)의 최솟값을 구하는 방법을 사용한다. 센트로이드 트리에서는 높이가 낮으니 일반적인 방법으로 하면 되고, HLD 풀이는 lazy propagation이 필요한데, lazy 값 f는 값 x를 가진 [l,r] 노드를 min(x,f-2*r)로 바꿔준다. 정확히는 min(x,f-2*l,...,f-2*r)인데, 두 값은 당연히 동일하다. 그냥 D(u)값을 관리하는 것이 아니라, D(u)-h(u)를(h는 chain 상에서 깊이) 관리해야 한다.

 

15565 귀여운 라이언

two pointer/inchworm/sliding window 기본 연습문제다.

 

15566 15567 15568 개구리

선호하는 연꽃이 2개 이하라는 점에서 2-SAT이 떠올려진다. 조건들은 어렵지 않고, 조건 간선을 만들때 시간복잡도에 문제가 생기지 않게 구현해야 한다.

 

15569 15570 15571 15572 블록

DP식 자체는 굉장히 흔한 유형이고, 어렵지 않게 계산할 수 있다. 초기항들 계산은 반복문으로 찾고, 나머지는 키타마사법을 이용해 빠르게 구할 수 있다.

 

15573 채굴

이분 탐색+BFS를 하거나 다익스트라의 변형 느낌으로 우선순위 큐를 사용해도 된다.

 

15574 15575 신호

가능한 모든 x좌표를 사용해야 함은 삼각부등식으로 어렵지 않게 보일 수 있다. 같은 x좌표 안에서 맨 위와 아래만 사용해도 된다는 것은 더 어렵지만 여전히 삼각부등식으로 보일 수 있다. 이제 정렬 후 x좌표의 구간들을 찾고, 현재 x좌표 기준 위/아래에 도달하는 최대 길이를 DP로 저장하면 된다. 지그재그 형태의 경로가 최적이라 추측할 수 있는데, 아니다.

 

15646 농부 후안은 바리스타입니다

2D펜윅 연습문제다. 일반적인 점 업데이트-구간 쿼리가 아니라 반대인데, 결국 한 쿼리에서 2D 부분합을 구하는 것임을생각하면, 부분합이 곧 자신의 값이 되게 업데이트를 4번 해서 만들 수 있다.

 

15647 로스팅하는 엠마도 바리스타입니다.

아무 정점에서 답을 구한 후, 인접한 정점으로 옮기면서 답이 얼마나 변하는지를 관찰하면, DP로 전처리하면 그 값을 구할 수 있음을 알 수 있다.

 

15648 추출하는 폴도 바리스타입니다

첫 번째 조건은 쉽다. 두 번째 조건도 구간 쿼리고, 어렵지 않다.

 

15896 &+ +&

&+는 쉽다. i번째 비트가 켜져있는 수의 개수를 저장하면 된다. +&는 어렵다. i번째 비트가 켜져있을 조건이 모든 합이 2^(i+1)로 나눈 나머지가 두 구간중 하나에 포함되어야 함을 알면 다양한 풀이가 가능하다. 

 

15901 소각로

재미없는 자료구조 연습문제이다. 대기열의 관리를 데크로 하고 종류를 세그먼트 트리/set으로 관리하는 방법이 있고, 대기열의 관리를 set으로 하고 번호를 세그먼트 트리로 관리하는 방법이 있다. 시간 측면이나 응용가능성 측면이나 앞 풀이가 더 좋아보인다.

 

16217 옥토끼나라

트리면 매우 쉬운 DP 문제다. 그래프로 바뀌면서 DFS 트리 상의 back edge가 추가되었다. 그 경우 위의 연결 컴포넌트와 합쳐진단 것을 고려하면, 위의 컴포넌트만 따로 관리하면 비슷하게 해결 가능하다.

 

16219 정렬하기

답이 항상 0 또는 -1일꺼라 생각할 수 있지만, 반례가 하나 있다. 증명 과정을 다시 살펴보자.

 

16220 회의

될것만 같은 그리디가 실제로 된다. 데이터가 약해서 이상한 그리디로도 맞을 것 같다.

 

16223 클러스터

Dynamic CHT를 세그먼트 트리의 노드로 만들면 된다. 리더 회사가 왼쪽인지 오른쪽인지에 따라 관리 방법이 다른데, 오른쪽이면 구간 쿼리 점 업데이트, 왼쪽이면 구간 업데이트 점 쿼리다. CHT를 lazy를 한다는 끔찍한 생각은 필요없고, 점 쿼리임을 이용하면 구간 업데이트를 할 때 노드들만 업데이트하고 점 쿼리를 리프까지 파고들면서 방문한 노드마다 쿼리를 날리면 된다.

 

16231 내가 그린 라이언 그림

멍청하게 smaller to larger 테크닉을 쓰면 털린다. 답에서 빠졌다가 다시 들어오는 경우가 있기 때문이다. 이 경우가 O(N)번 발생한다는 것을 증명한 후 현재 답 집합과 후보 집합을 관리하면 된다. 개수 조건만 유지한 채 세그먼트 트리 등으로 값을 관리해줘도 된다. 두 번째 풀이의 경우 정점마다 여러 쿼리를 물을 수 있다는 장점이 있지만, 세그먼트 트리로 관리하는 방법은 메모리에 추가로 로그가 붙는다.

 

16233 수학 문제

식을 써보면 진법처럼 하는 방법이 가능함이 증명 가능하다. 이외에도 다양한 방법이 가능하고, X의 자릿수 합을 100000으로 나눈 몫과 나머지를 각각 이용해 전처리 후 O(1)에 구하는 방법이 재미있었다.

 

17093 Total Circle

초심자를 위한 문제. 더 빠르게 해결도 가능하지만 너무 힘들다.

 

17094 Serious Problem

쉽다.

 

17095 Min-Max Subsequence

Subarray라 쓰지 않은 이유는 도저히 모르겠다. lower_bound 등을 활용해 O(NlogN)에 푼 사람이 많지만, 현재 기준 앞의 가장 오른쪽의 최솟값과 최댓값의 위치를 가지고 있으면 O(N)에도 된다.

 

17096 Tourist

최단경로 DAG를 생각해보면, 각 정점마다 나에게 오는 간선 중 하나는 이용해야 하며, 하나만 이용해도 된다. 그리고 그 하나는 비용이 최소인 간선일 때 최적이다.

 

17097 Truth Tellers

i가 가능할 조건은 Ai <= i <= Bi인 사람이 i명 이상인 것이다. Vi를 Ai <= i <= Bi인 사람의 수 - i라 정의하자. 구간에 1을 더하고 빼면서 V값이 0 이상인 가장 큰 인덱스를 찾는 문제가 되고, 세그먼트 트리에 lazy propagation과 함께 세그먼트 트리에서 이분탐색하는 테크닉을 이용하면 된다.

 

17098 Boomerangs

DFS트리에서 열심히 케이스 분석을 하자. back edge만 2개쓰는 경우는 의미가 없다. 한 간선이 절선이면 반드시 가능하니 먼저 세주자. 이제 각 정점 u에서 자신의 부모로 가는 간선이 사용된 부메랑의 개수를 셀 것이다. 이 간선이 절선이면 당연히 넘어간다. u의 서브트리에서 u 위로 가는 back edge가 1개뿐이고, 이 간선의 끝점이 u 또는 u의 부모인 것이 유일한 tree edge-back edge케이스다. 두 간선이 모두 tree edge인 경우는 좀더 귀찮은데, 자식 v로 가는 간선을 추가로 사용한다 하자. 마찬가지로 이 간선이 절선이면 넘어간다. 이제 v의 서브트리에서 u로 가는 back edge가 없고, 다른 자식 w의 서브트리에서 u 위로 가는 경우가 없어야 한다. v에서 u로 가는 back edge가 없다면 u 위로 가는 것이 반드시 있기 때문이다(절선이 아니므로). 꽤 다양한 값을 계산해야 하는데, dfs 과정을 생각해보면 대부분은 어렵지 않게 구할 수 있다. 이 외에도 다양한 풀이가 존재하는 것 같다.

 

17099 Contest

꽤 다양한 방법의 DP 풀이가 있다. 내 풀이는 현재 아직 끝나지 않은 대회들을 우선순위 큐로 관리하는 것이다. 우선순위 큐에서 뺄 때는 현재 시작점이 끝점보다 뒤에 있을 때이고, 그 때 현재까지 DP값들 중 최댓값을 갱신해주면 된다.

 

17100 Candy Boxes

냅색 문제의 응용이다. 전 포스트에서 올렸던 방식과 비슷하게 데크를 이용한 최적화를 사용하면 된다. STL을 쓰면 안타깝게도 TLE가 날 수 있다. 이러고 싶지 않았는데 펜윅이 너무 빨랐다.

 

17101 Dynamic Centroid

센트로이드가 정점이 하나 붙여지면 최대 거리 1만큼 이동함은 직관적이고 증명도 어렵지 않다. 움직이는 방향은 새 정점 방향이어야 하고, 센트로이드 기준 부모 방향인지는 dfs ordering으로 서브트리 안에 포함되어 있는지를 확인하면 되고, 자식 방향이면 새 정점에서 (거리-1)만큼 부모로 가거나, 센트로이드에서 자식들의 dfs ordering을 저장해놓은 뒤, lower_bound 등으로 해당하는 자식을 찾는 방법이 있다. 실제로 이동해야 하는지는 dfs ordering을 이용한 세그먼트 트리로 서브트리의 정점 개수를 구하면 된다. HLD로도 되는데, 그러지 말자.

 

17102 Grid Query

부분합이 어떻게 변화하는지를 관찰하면 함수들의 합으로 나타낼 수 있으므로, 스위핑을 섞으면서 각 계수들을 세그먼트 트리를 이용해 관리해주면 된다. 관리할 부분합이 2D 부분합인지, 행별 부분합의 구간합인지에 따라 조금은 디테일에 차이가 있고, 어느 방법이든 상관없을 것이다.

 

17365 별다줄

naive한 DP는 시간이 너무 오래걸린다. 문자열의 축약 후보들을 i가 이동함에 따라 트라이에서 이동시키면서 관리하면 된다는 것을 관찰하면 된다.

 

17376 룰렛

시작점과 끝점을 잇는 경로 상의 정점들을 반드시 모두 지나고, 순서대로 지나기 때문에, 결국은 자기에서 시작해 한번 이상 인접한 정점으로 이동할 확률, 자기에서 시작해 자기에서 끝나는 확률들을 구하면 된다. 이 값들은 그리 직관적이진 않지만 무한등비급수를 구하는 방법을 이용해 구할 수 있다. 이후에는 경로 곱 쿼리고, 다양한 방법으로 처리가 가능하다. 나는 LCA만 구하고 부분곱+역원으로 했고, LCA를 구하면서 구간곱 스파스 테이블을 함께 사용해도 된다.