환승 비용을 10^6으로 잡고 다익스트라를 돌리면 된다. (N-1) * 1000 < 10^6이어서 가능하다.
dp[n][k]를 n번째에서, k의 위치(상하좌우+원위치)에 있을 때의 최소 거리라고 정의하면,
\(dp[i][j] = min(dp[i][j], f(i + 1, k, nx, ny) + |nx - x| + |ny - y|)\)라는 식이 나온다.
누적 합을 이용하면 된다. dp[n][k]를 n번째에서 나눈 구간의 개수가 k개일 때의 경우의 수라고 정의하면,
\(0 \leq k \leq 3\)에서 해결할 수 있다.
\(dp[i][j] = dp[i - 1][j]\)는 편안함을 위해 써두고, 추가적으로는
\(sum(A) / 4 * j\)와 \(i\)번째까지의 누적 합이 같을 때만 갱신하면 된다.
\(dp[i][j] += dp[i - 1][j - 1]\)라는 식이 나오고, 답은 dp[n - 1][3]에 들어있게 된다.
답을 고정하고 정답 여부를 확인하는 대표적인 이분 탐색 문제이다. 답을 mid라고 했을 때, 정렬된 배열 A에서 두 수의 차가 mid보다 같거나 크도록 길이가 최대인 부분수열을 찾으면 된다. 그리고 이 길이를 문제에서 요구한 개수(?)와 비교하여 lo 혹은 hi를 갱신하면 된다. 비슷한 문제로는 삶의 질이 있다. 삶의 질은 앳코더에도 나온 갓문제이므로 모두가 이 문제를 풀어보았으면 좋겠다.
Tree Isomorphism의 기초 문제이다. 개념은 이 글에 매우 자세히 나와있다. 이 문제는 트리의 크기가 N<30인 것을 활용하여 비트마스킹으로 트리를 표현할 수 있다.
19160 - Regular Forestation (D4)
위 문제와 비슷하다. 센트로이드를 없애야 하는 것은 자명하고, 센트로이드를 없앤 후에는 나머지 서브트리들끼리 트리 동형인지 확인하면 된다.
----------
역시 골드 문제를 풀어야 정신 건강에 좋은 것 같다..
'백준 문제풀이' 카테고리의 다른 글
| 백준 16404 - 주식회사 승범이네 [Python] (0) | 2022.05.26 |
|---|---|
| 5/24 PS (3) | 2022.05.25 |
| 5/16~5/22 PS (0) | 2022.05.22 |
| 백준 13159 - 배열 [Python] (0) | 2022.05.02 |
| 백준 10227 - 삶의 질 [Python] (0) | 2022.04.29 |