tose33

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 인접한 모든 자리의 수가 1 차이 나는 수 가 계단수이다. (예: 45656) 0으로 시작할 수는 없다. d[n][a] : 길이가 n인 계단수중 끝 숫자가 a인 계단수의 총 개수 즉 길이가 n인 계단수의 총 개수 d[n] = d[n][0] + d[n][1] + d[n][2] + ... + d[n][9] n = 1 일때 1 2 3 4 5 6 7 8 9 n = 2 일때 10 21 12, 32 23, 43 34, 54 45, 65 56, 76 67, 87 78, 98 89 n = 3일때 210 121, 121, 32..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net d[n]: 카드 n장을 구매할때의 최대 비용 d[1]: 카드 1장을 구매할때의 최대 비용 d[2]: 카드 2장을 구매할때의 최대 비용 d[4]: 카드 4장을 구매할때의 최대 비용... 그렇다면 예제처럼 4장을 구매할 때의 경우를 살펴보면 1. d[0] + 4장을 한번에 구매하는 비용 p[4] 2. d[1] + 3장을 한번에 구매하는 비용 p[3] 3. d[2] + 2장을 한번에 구매하는 비용 p[2] 4..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net d[n] : n 자리로 구성할 수 있는 총 이친 수의 개수 일단 이친수의 조건은 1. 0으로 시작하지 않는다 2. 1이 두번 연속으로 나타나지 않는다. 이 두 조건중 2번째 조건이 중요하다. d[n]이 n 자리로 구성할 수 있는 총 이친수의 개수이다. 여기서 n번째 자리에는 0또는 1이 올 수 있고 이 두 가지 경우의 수를 합친 것이 d[n]이라고 볼 수 있다. - n번째 자리가 0으로..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 일단 d[n]을 규정해보면 d[n] : n이라는 숫자를 1,2,3의 덧셈으로 만들 수 있는 총 가지 수 그렇다면 d[1] = 1 1 d[2] = 2 1 + 1, 2 d[3] = 4 1 + 1 + 1, 1 + 2, 2+ 1, 3 d[4] = 7 1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1 // d..