woojin042의 블로그

https://www.acmicpc.net/problem/33960 PPC 2025 본 대회에서 끝내 못 푼 문제. 자신있는 DP 문제인데다가 이 문제만 풀면 1등 팀과 솔브수가 같은 상황이었는데... 못 풀어서 아무쪼록 한이 맺힌 문제이다.점화식은 간단하지만, 떠올리기가 어렵고 증명하기도 어려운 문제인 것 같아 풀이를 정리해본다. 아래보다 더 쉬운 증명이 있는지는 잘 모르겠다. 구간 DP를 이용하여 푼다. $dp[l][r]$: 구간 $[l, r]$에서 얻을 수 있는 점수의 최댓값이라 두자.Claim: 어떤 $l \le i $$ dp[l][r] = dp[l][i] + dp[i+1][r] + score(l, i, r) $$이 성립한다. 이 때 $score(l, i, r)$은 구간 $[l, i], [i+..

https://www.acmicpc.net/problem/3090 그리디 + 파라메트릭 서치를 사용하는 문제이다.문제를 풀고 블로그 풀이들을 보는데 내가 푼 방법이랑 많이 달랐고, 하나같이 이걸 어떻게 생각함(...) 식의 풀이여서 글을 쓰게 되었다.(시험 기간에 공부하기 싫어서 쓴 것도 있다.) 우선 보자마자 파라메트릭 서치를 쓰면 좋을 것 같다는 생각이 들었다.인접한 원소 간 차이의 최댓값을 한 번에 최소화하는 것보다, 인접한 원소 간 차이가 어떤 $d$ 이하가 되도록 연산을 수행할 수 있는지 판별하는 게 더 쉬워 보였기 때문이다. 여기서 한 가지 관찰을 할 수 있는데, 배열 $A$의 최소 원소를 $m$이라 두면, 연산을 최적으로 수행하고 얻은 결과 배열의 모든 원소는 $m$보다 크거나 같다.이는 ..