23.12.19 13:37 작성
·
154
0
안녕하세요 큰돌쌤!
문제를 풀다가 막혀서 질문드립니다!
http://boj.kr/54155bff977f43b3a75c1a59fc22430d
저는 ‘dp[현재위치][이동시간] = 모금액’ 이렇게 두고 활용했는데 1퍼 진행되고 틀렸습니다.
어떤 부분이 잘못되었는지 가르쳐주실수 있나요?
답변 2
0
2023. 12. 20. 16:41
안녕하세요 준영님 ㅎㅎ
제가 답변드리려고 했는데 잘 생각하셨네요. ㅎㅎ
ret = -INF;
ret = max(go(idx+1, sumFee+walk[idx].fee, walk[idx].time), go(idx+1, sumFee+ride[idx].fee, sumTime+ride[idx].time));
return ret;
}
말씀하신 것 처럼 이부분이 문제입니다.
DP라는 것은 로컬 optimum이 쌓여서 글로벌한 optimum으로 만드는 것이 핵심입니다.
즉, 각 정점은 해당 정점에서의 최적의 해를 담고 있어야 합니다.
그러나 준영님의 코드를 보면
go(idx+1, sumFee+walk[idx].fee, walk[idx].time)
go(idx+1, sumFee+ride[idx].fee, sumTime+ride[idx].time)
이 둘중의 max값을 해당 idx에 담고 있는데요. 얼핏보면 괜찮아보이지만..
이런 예를 생각하면 됩니다.
a -> b -> c -> d
d까지 가서 최대의 값을 가짐 -> c로 감 -> b로 감 -> a로 감.. 이렇게 해서 a가 정상적으로 max값을 출력하게 되지만..
DP배열을 보게 되면
아마 이런식으로 담겨있을 가능성이 높습니다.
dp[a] = 100
dp[b] = 100
dp[c] = 100
dp[d] = 100
즉, 간단한 그래프라면.. 어느정도는 될 거 같은데요. 복잡한 그래프라면 이 DP코드는 DP배열을 온전한 값으로 채우지를 못합니다. 그렇게 채우지를 못하고 해당 DP 배열끼리 비교도 안되구요.
그래서 틀리는 것 같습니다.
if(_time - a[here]._time >= 0)ret = max(ret, go(here + 1, _time - a[here]._time) + a[here].pay);
if(_time - b[here]._time >= 0)ret = max(ret, go(here + 1, _time - b[here]._time) + b[here].pay);
이런식으로 어떠한 가중치를 밖으로 빼서 해당 정점에서의 local optmimum을 만들고 그걸 기반으로 비교하게 만들어야 합니다.
즉.. 이런식으로 쌓이게 만들어야 합니다. 정점을 갈 때 + 가 되는 형식으로요 ㅎㅎ
dp[a] = 20
dp[b] = 50
dp[c] = 80
dp[d] = 100
하지만 나머지 부분이나 코드 구조는 전체적으로 깔끔하고 좋게 잘 짜셨습니다. ㅎㅎ
제가 말씀 드린 부분만 생각하시면 될 거 같아요.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
2023. 12. 20. 01:53
큰돌님 코드를 다시 생각해서 큰돌님 코드를 따라갔고 어떤 부분이 문제였는지 확인했습니다.
1) dp의 값이 올바르게 저장되지 못하고 있었음.
-> idx를 n까지 탐색하면서 리턴한 값이 되돌아오면서 관련된 dp값들을 전부 그 값으로 만들게되면서 다시 탐색해야하는데 dp에 저장된 값이 문제가 있었음.
2) 대소비교를 해서 문제를 해결하려 했으나, dp자체에 값이 잘못저장되어있는 문제로 해결되지 않았음.
감사합니다.