세상을 더 좋게

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net n = int(input()) dp = list([[1] * 10]) for _ in range(n): dp.append(list([0] * 10)) for i in range(1, n+1): for j in range(0, 10): for col in range(j+1): dp[i][j] += dp[i-1][col] print(dp[n][9] % 10007) ..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net n = int(input()) dp = [[0, 0, 0] for _ in range(n+1)] dp[1][0] = 1 dp[1][1] = 1 dp[1][2] = 1 for i in range(2, n+1): # no lion dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901 # left lion dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901 # right lion dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901 pr..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) RGB = [] for i in range(n): RGB.append(list(map(int, input().strip().split()))) for i in range(1, n): # red RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2]) + RGB[..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net import sys input = sys.stdin.readline dp = [0 for i in range(1000001)] dp[0] = 1 dp[1] = 1 dp[2] = 2 for i in range(3, 1000001): dp[i] = dp[i-1]%1000000009 + dp[i-2]%1000000009 + dp[i-3]%1000000009 t = int(input()) for i in range(t): n = int(input()) p..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net n, k = map(int, input().split()) dp = [[1] * (n+1) for _ in range(k+1)] for i in range(1, k+1): dp[i][1] = i for i in range(2, k+1): for j in range(2, n+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[k][n] % 1000000000) Point 갯수를 구하는 것이기에 갯수에 대한 규칙을 찾는 것이 중요 K \ N 1 2 3 4 1 1 1 1 1 2 2 3 4 5 3..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net import sys import math n = int(sys.stdin.readline()) dp = [0] * (n+1) for i in range(1, n+1): dp[i] = i for j in range(1, int(math.sqrt(i))+1): if (j*j) > i : break if dp[i] > dp[i - j * j]+1: dp[i] = ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n = int(input()) lst = list(map(int, input().split())) dp = [x for x in lst] for i in range(1, n): dp[i] = max(dp[i], dp[i-1]+lst[i]) print(max(dp)) Point DP의 핵심은 이전 결과값을 쓰느냐에 달려있다. 점화식이라는 규칙은 존재하지 않지만, 답을 얻기 위해서 어떤 메커니즘을 이용해야 하는..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net N = int(input()) A = list(map(int, input().split())) dp = [1] * N for i in range(N): for j in range(i): if A[j] < A[i]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) Point dp테이블을 이용해..