hosahn   2년 전

백준 문제는 아니지만, 책으로 공부를 하다 생각해봐도 답이 나오지 않아 질문드립니다. DP를 이용해 3점, 5점, 10점의 점수를 얻을 수 있는 게임에서 점수에 (예를 들어 13점) 도달할 수 있는 경우의 수를 찾으라는건데요. 여기까지는 문제없이 구현했으나 그 뒤에

(10,3) (3,10)과 같이 중복된경우를 제외하고 카운팅하는 함수를 구헌하시오. 라고 나와있는데, 이 부분을 도저히 모르겠네요. 이렇게 dp나 재귀에서 순서쌍의 중복을 제거하려면 어떻게 해야할까요?

팁만 간단히 주시면 구현은 제가 해 보도록 하겠습니다..부탁드립니다ㅠㅠ

lcr7324   2년 전

DP에서 순서쌍의 중복을 제거하는 방향으로 문제에 접근하면 풀기가 많이 어렵다고 생각합니다.

접근 방법 자체를 바꾸어야 합니다.

3점을 a번, 5점을 b번, 10점을 c번 넣었을 때 x점에 도달했다고 합시다.

그러면 문제는 이제 3a + 5b + 10c = x인 순서쌍 (a, b, c)의 갯수를 구하는 상황으로 바뀝니다.

여기부터는 이제 직접 고민해보시기 바랍니다.

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