dp

[백준/Swift] 2293 동전 1

문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2293 동전 1 제출 언어: Swift 알고리즘 분류: 다이나믹 프로그래밍 풀이 다이나믹 프로그래밍 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해 Table에 부분문제의 solution을 저장한다 항상 최적의 해를 보장하지만 Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다 알고리즘 설계 아래의 그림과 같이 다이나믹 프로그래밍 배열을 하나 생성하여 부분 문제의 해에 해당하는 값들을 넣어주었다 i : 해당 동전까지 사용할 수 있을 때 만들 수 있는 경우의 수 j : 가치의 합을 1원부터 k원까지..