저번 게시물에 2번 못풀었고 1번만 풀었다고 올려놓고 마무리했는데, 푸는방법을 알아냈습니다!
만약 1번 풀이 필요하시다면 후기 보시면 됩니다.
- 백준의 리조트 문제와 유사한 풀이(실패)
- 두 사람의 비용을 각각 계산하고 최소 비용을 더하는 방식의 풀이로 대회 당시에 접근하여 말렸습니다.
- 문제점: 두명이서 같이 산 경우 → 따로따로 DP배열을 만들어서 하면 같이 사는 케이스를 커버하는 것이 불가합니다. 누구한테 가격을 몰아준다면 다른 한명이 꿀빨고 튀고, 돈을 낸 사람은 그냥 다른 케이스 고려하는 것이 가능합니다. 이것을 고치기 위해 이런저런 똥고쇼를 했는데 안통함.
- 2차원 DP 풀이
- 대회 당시에는 생각하지 못했는데, n이 2000 이하이더라고요. 충분히 n^2으로 푸는 것이 가능한 문제였습니다!
- DP[i][j]는 i일과 j일까지 도달하기에 최소 비용이고, 위의 풀이와 동일한 로직을 쓰는 것이 가능합니다.
- i==j인 경우, 둘다 동시에 사는 경우를 포함시켜주면 됩니다.
나중에 BOJ에 나오면 소스코드 추가하겠습니다.