90841 [백준] 동전 9084 - JAVA 문제https://www.acmicpc.net/problem/9084전략동전으로 가능한 금액의 가짓수를 구하기 때문에 처음에 떠올린것은 완전탐색, 그리디 , DP이 중 테스트 케이스가 10 , 동전의 가짓수가 20 , 금액은 10000이다.완전탐색 : 동전의 종류별로 조합을 통해 금액 확인 ⇒ 시간복잡도가 20! * 10으로 너무 크다그리디 : 값이 큰 동전을 먼저 사용하는 방식은 최적해를 보장하지 않는다.시간복잡도까지 고려해서 DP로 접근하는것이 맞다고 생각해 고민하였다.dp배열을 금액에 따른 가짓수로 두었을때 2중 for문으로 동전별로 가능한 금액의 가짓수를 세는것dp[j] += dp[j - coin] (단, j - coin >= 0일 때)하지만 dp배열이 1차원일 경우 5+7과 7+5처럼 중복으로 .. 2024. 8. 13. 이전 1 다음