[Python] 1737번 Pibonacci
https://www.acmicpc.net/problem/1737 1737번: Pibonacci 첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 22/11/08 신박한 2차원 DP문제로, 처음에는 재귀를 이용한 탑다운 방식으로 접근했었으나, 재귀 시간이 너무 오래 걸려 바텀업 방식으로 전환하여 풀 수 있었던 문제다. 문제 접근 방식: 이 문제를 보면, 기존 피보나치수열의 점화식과는 다르게 아래와 같은 점화식을 가지고 있다. 맨 처음 생각한 풀이는 위의 점화식을 재귀로 구현하고, DP테이블은 딕셔너리로 구현함으로써 하려고 했다. 딕셔너리의 키는 실수 연산을 통해서 구현하려고 했다. 근데, 이..
[Python] 9084번 동전 / 3067번 Coins
https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 22/10/03 배낭 문제 중 하나인데, 1차원 ..
[Python] 11057번 오르막 수
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 22/10/03 전형적인 DP문제로, 나는 이차원 배열을 사용하여 문제를 해결하였다. 문제 접근 방식: 나는 DP[i][j]의 정의를 다음과 같이 정의했다. DP[i][j] = i자리 숫자일 때, j로 끝나는 오르막 수의 개수 이와 같이 정의를 하면, j가 0일 때, 1일 때, ..., 9일 때 모두 비슷한 점화식을 가진다. 오르막 수의 정의 상 이전 숫자보다 ..
