2024.04.15. ~ 2024.04.21.

백준 4 문제.

 

1. BOJ 20052 : 괄호 문자열 ? - P4

Prefix Sum + Segment Tree 문제.

 

'('를 +1, ')'를 -1로 치환해서 푸는 문제인데, 옳은 문자열이라면 저렇게 치환했을 때의 총합은 0이어야 한다.

또한, 중간에 누적합의 결과가 음수가 나온다면 ')'의 개수가 더 많아지는 경우가 생기므로 옳은 문자열이 될 수 없다.

 

따라서, Prefix Sum을 미리 구하고 이에 대해서 Segment Tree를 생성하면 Min query로 중간 누적합 결과가 음수가 나오는지 판별도 쉽게 가능하다. Prefix Sum을 이미 구했으니 총합이 0이 되는지의 여부도 쉽게 파악이 가능하다.

 

오랜만에 풀어본 세그 문제.

 

2. BOJ 26093 : 고양이 목에 리본 달기 - G3

DP 문제.

 

dp[i][j]를 i번째 고양이에게 j번째 리본을 달았을 때의 만족도 합의 최댓값이라고 하자. 그렇다면 dp[i][j] = a[i][j] + max(dp[i-1][k] (1 <= k <= K and k != j)) 이런식으로 점화식을 세울 수가 있다. 그런데, 이렇게만 점화식을 세우고 푼다면 O(NK^2)라서 TLE가 난다. 따라서, i-1번째 고양이가 j번째 리본을 단 케이스를 제외한 것 중에서의 최댓값을 빠르게 구해야하는데, 이를 multiset을 활용해서 O(logK)만에 구할 수 있다. 따라서 총 시간복잡도는 O(NKlogK).

 

재밌던 문제였다.

 

3. BOJ 11725 : 트리의 부모 찾기 - S2

DFS 문제.

 

그냥 트리의 부모찾는 문제로 트리의 루트부터 DFS를 하여 찾는 문제이다.

아직도 트리 관련 문제를 50문제 이상 안 풀었어서 푼 문제.

 

4. BOJ 31713 : 행운을 빌어요 - S4

Math 문제.

 

3*A <= B <= 4*A를 만족한다면 모든 줄기 및 잎을 사용해서 클로버를 만들 수 있다.

이를 활용해서 A와 B의 값을 하나하나씩 올려 풀면 된다.

의외로 이렇게 구현했는데 풀려서 놀랐던 문제.

 

요새 문제 푸는게 약간 버거운 것 같다.

이외에도 Lumine 작업도 계속 미뤄두고 있고... 좀 반성이 필요하다.

아무튼 이번 주 일지도 여기서 끝.