일단 이 문제가 아니라 33989번: 벚꽃과 단풍 문제에 대한 질문인 것 같습니다.
현재 구현에서 dp[i+1][1]은 질문자님이 언급하신 것과 달리 D가 존재하지 않는 경우도 같이 고려하고 있습니다. 즉 min(dp[N][0], dp[N][1])가 아니라 dp[N][1]만을 출력하더라도 정답이 될 것입니다.
33989번 - 벚꽃과 단풍
일단 이 문제가 아니라 33989번: 벚꽃과 단풍 문제에 대한 질문인 것 같습니다.
현재 구현에서 dp[i+1][1]은 질문자님이 언급하신 것과 달리 D가 존재하지 않는 경우도 같이 고려하고 있습니다. 즉 min(dp[N][0], dp[N][1])가 아니라 dp[N][1]만을 출력하더라도 정답이 될 것입니다.
댓글을 작성하려면 로그인해야 합니다.
s2k616 1년 전 1
제가 dp가 미숙하다보니 어렵게 풀었습니다.
바로 다음날 제 코드를 제가 리뷰하는데 제가 왜 이렇게 풀었는지, 왜 맞았는지 모르겠습니다.
문제는 단순히 모든 어떤 B는 모든 어떤 D보다 왼쪽에 있도록 하게 만드는 뒤집기 최솟값을 구하는 문제입니다.
dp[MAX_N][2]를 선언하고 그 값은 뒤집은 횟수로 채울겁니다.
dp[i+1][1]은 s[0]~s[i]까지 'D'가 존재할때 뒤집은 최소 횟수입니다.
dp[i+1][0]은 s[0]~s[i]까지 'D'가 존재하지 않을때 뒤집은 최소 횟수입니다.(제가 'D'를 'B'로 바꿔버린 경우도 포함힙니다.
그래서 마지막에 min(dp[N][0], dp[N][1])을 출력하고 끝낼 것입니다.
떠올린 로직은 다음과 같습니다.
수정 전 로직
만약 s[i]가 'B'라면 -> 이전에 'D'가 등장한 경우 -> 뒤집어야 함
-> 이전에 'D'가 등장하지 않은 경우 -> 뒤집지 않아도 됨
만약 s[i]가 'D'라면 -> 이전에 'D'가 등장한경우 -> 뒤집지 않아야 함
-> 이전에 'D'가 등장하지않은경우 -> 뒤집거나 뒤집지 않거나.
이러다가 치명적인 반례를 발견했고, 로직을 수정했습니다.
만약 s[i]가 'B'라면 -> 이전에 'D'가 등장한 경우 -> min(뒤집거나, 이전에 'D'가 존재하지 않았던 경우)
-> 이전에 'D'가 등장하지 않은 경우 -> 뒤집지 않아도 됨
만약 s[i]가 'D'라면 -> 이전에 'D'가 등장한경우 -> 뒤집지 않아야 함
-> 이전에 'D'가 등장하지않은경우 -> 뒤집음.(여기도 수정됨)
근데 지금 다시보니 수정된 부분이 말이 안됩니다.
dp[i+1][1]은 s[0]~s[i]까지 무조건 'D'가 있다는 건데, 어떻게 s[i]가 'B'면서 s[0]~s[i-1]이 전부 'B'인 경우가 값이 될 수 있겠습니까?
지금 다시보니 틀렸다고 생각됩니다. 'D'랑 'B'를 헷갈린 것 같습니다.
근데 왜 맞았는지 모르겠습니다. 제가 dp를 못하긴 하지만 이 문제를 dp로 풀 때 고려해야 할 게 두가지같은데, 어떻게 이 코드가 만족한 걸까요?..
마지막으로 정리하자면 제가 궁금한 점은 코드가 틀렸는지가 아니라.. 왜 이 코드가 문제를 풀 수 있었는지 전혀 모르겠습니다.
추가로 이러한 고민을 해결하면 ps실력이 늘 것이라 생각했는데 이런 고민은 그냥 시간만 날리는 것일까요?
지금 3시간째 고민하고 있는데 모르겠습니다. 고수분들의 도움을 부탁드립니다..