9084
-
[Python] BOJ 9084 : 동전코딩테스트/백준 2024. 9. 29. 22:00
https://www.acmicpc.net/problem/9084 요구사항시간 제한 1초 코인의 종류와 주어진 금액을 만드는 모든 방법, N과 M 따라서 O(N*M) 이 되겠다. 20 * 10000 이니 2만정도.. O(NlogN)정도메모리 제한 128MB메모리 제한은 128MB로 터지진 않을 거 같다. 이유는 리스트의 크기가 해봐야 dp 테이블 M+1 개, 이니깐.동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 프로그램설계처음엔, 2차원 DP 테이블을 만들어서 하려고 하니 너무 복잡해서 다른 관점에서 보려고 노력했다. 따라서 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 함수의 로직은1차원 DP 테이블을 초기화 한다. dp = [0] * (주어진 금액 + 1)dp..