최근에 재미있는 풀이를 발견해서 정리해본다. 이 풀이는 결과값(정답)을 구해야 하는데, 결과값을 구하기 위해 계산하는 과정에서 결과값이 필요한 경우를 말한다. 말이 이해가 안 갈수가 있는데, 밑에 문제를 보면 어떠한 유형인지 알 수 있을 것이다.
푸는 방법을 간단히 요약하자면, 결과값을 parametric search를 이용해 임의로 정하고, 계산해서 나온 결과값이랑 임의로 정한 결과값을 비교해 결과값을 찾으면 된다.
BOJ 21343 - Great Expectations
위 문제를 요약하면, 스피드런을 하는데 특정 시간마다 trick이 있다. 이 trick은 어려워서 특정 확률로 실패할 수 있는데, 실패할 경우 추가 시간 패널티를 얻게 된다. 그리고 이렇게 추가 시간 패널티를 더해서 r시간보다 작아야 한다. 그리고 추가로 스피드런을 하다가 리셋을 할 수 있는데, 이러면 처음부터 다시하나 흘러간 시간은 그대로이다(스피드런을 할 때 리셋을 하고 다시 녹화를 한다고 생각하면 된다). 이럴때 스피드런을 완료하는데 걸리는 시간의 기댓값을 최소화하는 문제다.
요약한 것을 봐도 잘 이해가 안 가는데, 예제입력 1을 보면 이해가 조금은 된다.
일단 dp식을 \( dp[i][j] = i\)번째 trick부터 끝까지 진행하고, \( j\)만큼 패널티를 먹을 때 최소 기댓값 으로 정하자.
\(dp[i][j]\)를 구할 때 먼저 \(t[i] - t[i-1]\)를 더한다. 그래야 다음 \(i-1\)에서 기댓값을 구할 때, \(i-1이후~\) 값을 구할 수 있기 때문이다. 그리고 이제 성공할 때 경우하고 실패할 때 경우의 기댓값을 구해야 한다.
만약 성공하는 경우에는 패널티가 없기 때문에, 그냥 \(dp[i+1][j]\)를 더하면 된다. 만약 실패하는 경우에는 패널티를 먹고 계속 진행하거나, 리셋을 해서 처음부터 다시 하는 경우가 있을 수 있다. 전자는 단순히 \(dp[i+1][j+err[i]] + err[i]\)를 더하면 되는데, 후자는 딱히 이전 dp값으로 표현을 할 수가 없고, 그냥 결과값을 넣어야 한다. 식을 정리하면,
\[dp[i][j] = t[i] - t[i-1] \] \[+ p[i] * dp[i+1][j] \] \[+ (1-p[i]) * min(dp[i+1][j+err[i]] + err[i], 결과값)\]
이 된다. 결과값을 구하기 위해 dp를 계산하는데 dp 계산식에 결과값이 들어가는 모순?이 생겨버린다. 이 문제를 해결하기 위해, 결과값을 \(k\)로 정하고, 계산한 결과값을 \(k\)랑 비교해서 parametric search로 찾으면 된다. 만약 k보다 더 작은 결과값이 나오면, 실제 결과값은 더 작을 것이기 때문에 더 작게 조절하고, 더 큰 결과값이 나오면 실제 결과값은 더 클 것이기 때문에 더 크게 조절하면 된다.
BOJ 6141 - Sightseeing Cows
\( \frac { \sum { \text {fun values} } } { \sum{ \text { path cost } } } \) 를 최소화하는 사이클을 찾는 문제이다.
실은 풀이가 완전히 이해가 되진 않았는데, 그래도 써본다.
일단 \(결과값 = \frac { \sum \text{fun values} } { \sum \text{path cost} } \) 이 식을 변형하면 \(결과값 * \sum { \text{path cost}} - \sum { \text { fun values } } = 0 \) 이 된다. 이렇게 변형한 이유는 그래야 경로를 돌면서 \( 결과값 * \text{edge cost} - \text{fun value} \) 로 그때 그때 업데이트가 가능하게 되서 간선의 비용을 바꿀수 있기 때문이다.
변형된 계산식으로 계산했을 때, 만약 음수 사이클이 나온다면 변형 식의 값이 음수라는 뜻이고, 이는 \(k\)보다 실제 결과값이 더 크다고 볼 수 있다(그래야 변형 식의 값이 커지기 때문에). 반대로 음수 사이클이 없다면 실제 결과값이 더 작다고 볼 수 있다. 이것을 parametric search로 실제 결과값을 찾으면 된다.
꽤나 신선한 방법이라서 이러한 풀이로 푸는 문제들을 더 풀어보고 싶은데, 딱히 이런 방법을 표현하는 용어도 없어서 찾기가 어렵다. 그나마 이분 탐색/매개 변수 탐색 태그로 찾아보면 좀 나올지도?