2293

DP가 어렵다고 느끼는 이유는 점화식을 세워야 한다. 이 문제는!! DP를 연습하기 좋은 문제지 않나 생각해본다. 위 두 블로그를 통해서 방법은 같지만 서로 다른 점화식을 확인할 수 있었다. 요약하자면 다음과 같다. 문제에서는 k원이라고 주어졌지만, 테스트 케이스 10원으로 예시로 든다면 1원 부터 테스트 케이스(원) 까지 만들 수 있는 방법을 전부 고려해보는것이 가장 첫 번째 스텝인것 같다. 이때 입력으로 주어진 동전을 고려해 봐야 하는데 테스트 케이스로 주어진 1원, 2원 그리고 5원을 고려해보자. 1원으로 1~10원을 만들 수 있는 방법은 각각 1원은 1가지 방법 2원도 1가지 방법 ... 10원도 한가지 방법이다. 1원으로 뭔 짓을 해봤자 1가지 방법밖에 나올 수 없다. 2원으로 1~10원을 만들..