세상을 더 좋게

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net n = int(input()) def sol(n): if n % 2 != 0: return 0 else: dp = [0] * (n + 1) dp[0] = 1 dp[2] = 3 for i in range(4, n + 1): dp[i] = dp[i-2] * 3 for j in range(i-4, -1, -2): dp[i] += dp[j] * 2 return dp[n] print(sol(n)) Point 타일문제로서 규칙을 먼저 찾아보면 홀수는 성립되지 않고 짝수만 성립된다는 것을 우선 알 수 있다. 그리고 n=..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net n = int(input()) arr = list(map(int, input().split())) dpUp = [0 for i in range(n)] dpDown = [0 for i in range(n)] dpMix = [0 for i in range(n)] for i in range(n): for j in range(i): if arr[j] < arr[i] and dpUp[i] < dpUp[j]: dpUp[i] =..

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n = int(input()) arr = list(map(int, input().split())) dp = [[0,0] for i in range(n)] dp[0][0] = [list[0], -999999999] for i in range(n): for j in range(i): dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]) dp[i][1] = max(dp[i-1][0..

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

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net N = int(input()) numbers = list(map(int, input().split())) dp = numbers[:] dp[0] = numbers[0] for i in range(1, N): for j in range(i): if numbers[j] < numbers[i]: dp[i] = max(dp[i], dp[j] + ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net n = int(input()) array = [0]*10000 for i in range(n): array[i] = int(input()) # dp[i] is max wine dp = [0] * 10000 dp[0] = array[0] dp[1] = array[0]+array[1] dp[2] = max(array[2]+array[0], array[2]+array[1], dp[1]) for i in ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net n = int(input()) dp = [] for i in range(n): dp.append(list(map(int, input().split()))) k = 2 for i in range(1, n): for j in range(k): if j==0: dp[i][j] = dp[i][j] + dp[i-1][j] elif i == j: dp[i][j] = dp[i][j] + dp[i-1][j-1] else : dp[i][j] = max(dp[i-1][j-1], dp[i..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net tc = int(input()) for _ in range(tc): n = int(input()) dp = [] for _ in range(2): dp.append(list(map(int, input().split()))) dp[0][1] += dp[1][0] dp[1][1] += dp[0][0] for i in range(2, n): dp[0][i] += max(dp[1][i-1], ..