kcsoo1234   2년 전

야밤에 질문 올립니다...

예시나 다른 케이스들도 다 정답이 나오는데 왜 자꾸 틀리다고 나올까요? 반례가 궁금합니다

djm03178   2년 전

dp[1000000]에 접근하기 위해서는 dp의 크기가 최소 1000001이어야 합니다.

그리고 이 코드는 dp라고 부르기 어렵습니다. 현재 N을 보고 최적이 되는 다음 N을 직접 골라 그 방향으로만 나아가기 때문입니다. dp가 되려면 모든 가능성을 열어두고 다 해본 뒤 그 중 최적을 고르는 형식이 되어야 합니다. 3으로 나누어 떨어진다고 해서 바로 3으로 나누는 게 최적이라는 보장도 없고, 1을 뺀 뒤 3으로 나눌 수 있다고 해서 그렇게 하는 게 최적이라는 보장도 없고, 2로 나누어 떨어진다고 해서 2로 바로 나누는 게 최적이라는 보장도 없습니다. 그저 추측에 불과합니다.

kcsoo1234   2년 전

수준 높은 답글 감사합니다. 제가 dp 알고리즘을 접한지 얼마 되지 않아 몇 가지 질문이 더 있습니다.

1. dp 알고리즘에서 모든 가능성을 열어두고 다 해본다고 하셨는데 그럼 조건에 따라 상황을 제외시키는 if문은 어떠한 경우에도 사용이 불가한가요?

2. bottom up과 top down 이렇게 2가지 방식으로 구현이 가능하다고 공부했습니다. 문제에 따라 유리한 방법이 있는지 여쭤보고 싶습니다. 아니면 한 가지 방법만을 고수해도 괜찮습니까?

djm03178   2년 전

1. 어떤 방향으로 가는 것이 최적이라는 것을 증명할 수 있다면 해도 됩니다. 하지만 이 문제에 대한 그리디 기법을 증명한 사례는 보지 못했습니다. 중요한 것은 추측만으로 더 유리할 것 같이 보이는 길을 고르는 것은 위험하다는 점입니다.

2. 각기 알아두면 더 편리한 상황들이 있습니다. 둘 다 알아두시는 게 이후에 좀 더 특이한 형태의 점화식이 등장했을 때 대처하기 좋을 거라고 생각합니다.

kcsoo1234   2년 전

많이 배우고 갑니다. 다음에 기회가 되면 또 여쭤보겠습니다:)

댓글을 작성하려면 로그인해야 합니다.