크롱의 Dev Log

문제 링크: www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 화폐단위가 100씩 곱한 값으로 끊어진다는 것을 캐치하면 쉽게 풀리는 문제이다. 현재 지불해야하는 금액 중 100으로 나눈 나머지는 어차피 100 이하의 금액인 동전(1, 10, 25)로만 지불할 수 밖에 없다. 따라서 1~99 금액에 대한 필요한 동전 개수를 계산해 dp..

문제 링크: www.acmicpc.net/problem/1003 피보나치 함수를 구현하는 여러 방법이(재귀 함수 등)있지만 기존의 값을 저장하지 않고 새로운 숫자의 피보나치 값을 구하려면 이전 값까지 계속 다시 연산해야 한다. 예를 들어, 새롭게 숫자 5의 피보나치 결과를 구하려면 이전에 피보나치 4, 3, 2, 1을 구했더라도 새롭게 다시 연산해야 한다. 다른 숫자에 대해서도 기존에 연산한 결과를 활용하지 못하고 새롭게 연산해야하므로 답은 제대로 나오겠지만 시간이 많이 걸리게 된다. 이 문제는 제한시간이 0.25초로 위 방법을 사용하면 시간 초과가 뜬다. 그럼 어떻게 시간 초과를 피할 수 있을까? 답은 다이나믹 프로그래밍(동적 계획법)이다. 다이나믹 프로그래밍(동적 계획법)이란? 기존의 연산 결과를 저..