2024.03.18. ~ 2024.03.24.

백준 5 문제.

 

1. BOJ 19587 : 객실 배치 - G1

DP + Exponential by Squaring 문제.

 

DP[n]을 n층 건물을 채우는 방법의 수라고 식을 두면, DP[n] = 2 * DP[n-1] + DP[n-2] 이런 점화식이 나온다.

저 점화식은 사실 DP[1] ... DP[5] 까지 경우의 수를 그리면서 알게 된거긴 하지만, 점화식을 설명해보자면...

n층 건물은 n-1층의 건물에서 한 층 더 쌓아올린 거라고 생각해도 된다.

 

그래서 우리가 생각해야할 경우의 수는...

 - n-1층까지 쌓아올린 후에 n층에 아무도 살지 않는 경우의 수 = DP[n-1]

 - n-1층까지 쌓아올린 후, n-1층 오른쪽에 아무도 안 사는 경우의 수 = DP[n-1] - n-1층 오른쪽에 사는 사람이 있는 경우

 - n-1층까지 쌓아올린 후, n-1층 왼쪽에 아무도 안 사는 경우의 수 = DP[n-1] - n-1층 왼쪽에 사는 사람이 있는 경우

 

이를 모두 더 해보면... DP[n] = 3 * DP[n-1] - (n-1층 오른쪽에 사람이 사는 경우의 수 + n-1층 왼쪽에 사람이 사는 경우의 수) =  2 * DP[n-1] + (n-1층에 사람이 아무도 살지 않는 경우의 수) = 2 * DP[n-1] + DP[n-2]가 나온다.

 

그래서 이 점화식을 기반으로 행렬을 세우고 분할 정복을 활용해서 O(logN)만에 거듭제곱을 시행하고 행렬곱을 해주면 된다. 

 

2. BOJ 12928 : 트리와 경로의 길이 - P4

DP + Math 문제.

 

단순 경로가 2인 경로들 개수는 모든 노드에 대해서 해당 노드를 경로의 중간에 있는 노드라고 했을 때에, 해당 노드와 연결된 다른 두 노드를 선택하는 경우의 수들의 합이라고 할 수 있다. 1, 2, ..., N번 노드와 연결된 노드들의 개수 = 연결된 edge들의 개수를 각각 e_1, e_2, ..., e_N으로 표현하면 다음과 같이 식을 정리할 수 있다.

 

e_1 + e_2 + ... + e_N = 2*(N-1)

S = e_1C2 + e_2C2 +... + e_NC2 = (e_1^2 + e_2^2 + e_3^2+ ... + e_N^2)/2  - (e_1+e_2+...+e_N)/2

 e_1^2 + e_2^2 + e_3^2 +... e_N^2 = 2*S + 2*(N-1)

 

그래서 우리는 n개의 노드들에 대해서 degree의 총 합이 2*(N-1)가 되도록 적절히 분배했을 때에 e_1^2 + e_2^2 + e_3^2 +... e_N^2 = 2*S + 2*(N-1) 를 만족하는 경우가 있는지를 파악해야 한다. 이를 위해서 DP식을 아래와 같이 세워두고 memoization을 돌려보면 쉽게 풀 수 있다.

 

- dp[n][k][val] = n번째 노드까지 degree를 2*N-2-k개를 분배했고, e_1^2 + e_2^2 + e_n^2 = val 일때, 나머지 N-n개의 노드들로 e_1^2+ e_2^2 + ... + e_N^2 = 2*(S+N-1)를 만족하는 경우가 존재하는 가?

 

핵심 아이디어가 매우 재밌었던 문제. 이외에도 여러 다른 풀이가 존재하는 것 같다.

 

3. BOJ 21925 : 짝수 팰린드롬 - G3

Greedy +  Stack + Deque으로 풀었다.

 

먼저, 팰린드롬을 Greedy하게 가져갈 수 있는건 다음과 같다.

만약에 팰린드롬 S의 맨 앞에서부터 시작하는 substring s도 팰린드롬이라면 S는 s - <팰린드롬> - s 구조를 띄고 있을 것이다. 따라서, S를 s - <팰린드롬> - s 이렇게 세 개로 더 쪼갤 수 있기에 Greedy하게 가져갈 수 있다.

 

또한, Stack과 Deque을 활용해서 뒤랑 같으면 pop, 아니면 empty가 되기 전에 pop했던 것들 전부 되돌리고 새로운 값을 push하는 방식으로 구현해서 팰린드롬 판별을 좀 더 쉽게 할 수 있다. 이렇게 구현하면 각 element 별로 최대 O(N)번 pop, push가 되므로 총 시간복잡도는 O(N^2)이 될거다.

 

DP랑 Greedy는 역시 연습을 더 해야겠다...

 

4. BOJ 1289 : 트리의 가중치 - P3

Tree DP + math 문제.

 

각 노드별로는 해당 노드 아래 간선들을 지날 때 가능한 비용들의 합을 기록해야하고,

별개로 DFS를 하면서 서브트리 간의 가능한 경로들의 가중치 합도 따로 기록하면된다.

내가 DP로 플레 자력솔을 할 줄은 몰랐다. 그래도 내가 자력솔 할 정도면 P4도 될 수 있을 것 같아 P4로 기여해두었다.

 

4. BOJ 14449 : Balanced Photo - P5

나는 Merge Sort Tree로 풀었다.

 

Merge Sort Tree로 구현한다면 쿼리 내에서 Binary Search를 돌려 구간 내에서 k보다 큰 값들의 개수를 쉽게 알 수 있다. 

그래서 그냥 각 v[i] 별로 앞 뒤 구간의 v[i]보다 큰 값들의 개수를 찾아서 풀었다.

 

정해는 Segment Tree라고 하는데... 좀 비슷하게 풀리지 않을까 싶다.

 

5. BOJ 13147 : Dwarves - G2

Topological sorting 문제.

 

난쟁이들 간의 키의 대소관계를 그래프로 나타내면, 대소관계가 꼬이는 경우 = 사이클이 존재하는 경우가 된다.

따라서, 해당 그래프가 DAG인지 아닌지를 확인하면 되므로 Topological sorting을 박아서 모든 정점의 indegree가 0이 되는지를 확인하면 된다.

Topological sorting 연습하기 좋은 문제라 생각한다.