https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 생각하기 너무 힘들었다.. 그래서 다른 사람의 해결책을 보면서 원리를 이해했다. 이 문제에서의 핵심은 메모리를 관리하는 것이다. 그래서 동전의 사용을 dp로 저장하였다. 동작 방식은 먼저 0부터 k까지의 수를 만드는 과정을 기록할 배열을 둔다고 생각한다. 예를 들어 n=3 k=10이고 1,2,5가 동전으로 주어졌다고 생각해보자.(설명에서 헷갈리는 것을 줄이기 위해 동전을 one,two,..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 유튜브에서 DP관련 영상을 본김에 DP문제를 풀어보기로 했다. 위의 문제는 주어진 코드로 피보나치 함수를 구형하면 시간초과가 난다. 그래서 이것은 중복적으로 계산하는 횟수를 생략하여 DP배열에 저장하고, 그 값을 이용하는 것이다. 즉, 피보나치 수열은 fibonacci(3)=fibonacci(2)+fibonacci(1)이고, fibonacci(4)=fibonacci(3)+fibonacci(2)이니까 이전의 값을 저장해두면 다시 반복해서 계산하는 과정을 생략하고, 값을 구할 수 있다. 즉, fi..