세상을 더 좋게

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net N = int(input()) dp = [0 for _ in range(91)] for i in range(1, N+1): if i == 1: dp[i] = 1 elif i == 2: dp[i] = 1 else: dp[i] = dp[i-1] + dp[i-2] print(dp[N]) Point 점화식을 찾아내서 활용한 DP 문제 점화식이 이전 값들을 사용하기 때문에 DP방식을 사용하면 된..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 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) res_max = max(dp) print(res_m..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 MOD = 1000000000 for i in range(2, N+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N]) % MOD) Poi..

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net n = int(input()) p = [0] + list(map(int, input().split())) dp = [False for _ in range(n+1)] # 기존의 카드만들기에서 DP테이블을 [0]으로 두던 것과는 다르게 False를 주었다. # 그 이유는 최소값을 구해야 하는데 [0]이 끼어 있으면 방해되기 때문 for i in range(1, n+1): for k in range(1, ..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net n = int(input()) dp = [0] * 1001# DP 테이블 만들기. 범위가 1000까지이므로 1001까지 받는다. dp[1] = 1 dp[2] = 3 for i in range(3, 1001) :# 점화식을 이용하여 바텀업 방식으로 DP 알고리즘 이용 dp[i] = dp[i-1] + 2 * dp[i-2] print(dp[n] % 10007) Point DP를 이용한 알고리즘 이전 11726문제에서 점화식이 약간 ..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net n = int(input()) p = [0] + list(map(int,input().split()))# 주어진 갯수에 맞는 가격들을 p라는 리스트로 받는다 dp = [0 for _ in range(n+1)]# DP 테이블 for i in range(1,n+1): for k in range(1,i+1):# dp[i]의 최댓값 찾기 dp[i] = max(dp[i], dp[i-k] + p[k]) print(..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net T = int(input()) nums = [] # 수들을 담기 위한 리스트 dp = [0] * 11 # DP 테이블. 최대 11이므로 11까지 받는다. dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4, 11) : # 귀납법으로 규칙을 찾다보면 아래와 같은 규칙이 나온다는 것을 알 수 있다. dp[i] = dp[i-3] + dp[i-2] + dp[i-1] for _ in range(T) : # 차례대로 점화식에 대입하여 출력 n = int(input()) pr..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net n = int(input()) dp = [0] * 1001# DP 테이블 만들기. 주어진 범위가 1000이라서 1001까지 받는다. dp[1] = 1 dp[2] = 2 for i in range(3,1001): dp[i] = dp[i-1] + dp[i-2]# 발견한 점화식을 사용. 피보나치 수열과 같다. print(dp[n] % 10007) Point DP를 이용한 알고리즘 문제 바텀업 방식으로 작은 문제 해결을 바탕..