WoohyunKing의 개발 성장일지

이번 문제는 이전에 풀었던 01타일 문제와 매우 유사한 문제로, 다음과 같은 조건을 만족하는 이친수의 개수를 구하는 문제이다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 이러한 패턴의 문제는 n=1 부터 차근차근 구하면서 점화식을 찾아내는 것이 핵심인데, n=1부터 차례대로 값을 구해본 결과 다음과 같은 점화식을 얻을 수 있었다. dp[1] = 1, d[2] = 1 dp[n] = dp[n-1] + dp[n-2] (n>=3) 이러한 점화식을 도출한 후, DP 테이블에 저장하여 쉽게 풀 수 있었던 DP 문제였다 :)

import sys input = sys.stdin.readline n = int(input()) data = list(map(int,input().split())) dp = [1]*n for i in range(1,n): for j in range(i): if data[i] < data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 병사의 수 N과 각 병사의 전투력 정보를 입력받은 뒤, 모든 병사를 내림차 순으로 정렬하되 남아있는 병사의 수가 최대가 되도록 만드는 문제이다. 해당 문제는 이전에 풀이했던 LIS 문제와 상당히 유사한 문제인데, 문제에서 열외시키는 방법으로 수행한다는 말 때문에 쉽게 떠올리지 못한 것 같다. LIS 문제란 특정 조건을 ..

n = int(input()) array = list(map(int,input().split())) dp = [1]*n for i in range(n): for j in range(i): if array[i] > array[j]: dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) 이번 문제는 주어진 수열에서, 증가하는 부분 수열 중에 가장 긴 부분 수열을 구하는 문제이다. 처음 이 문제를 풀 때는 값이 증가하는 경우와 값이 감소하는 경우를 나눠서 풀었었는데, 결국 틀리는 경우의 수가 많아서 이 방법은 포기하기로 하였다. 그래서 다른 분의 풀이를 참고해본 결과, 이 문제를 풀기 위한 핵심 아이디어는 다음과 같다. 먼저 초기에 모든 수들이 각자 가지는 길이는 1이므로 1차원 리..

n = int(input()) price = list(map(int,input().split())) dp = [[0]*(n+1) for _ in range(n+1)] for i in range(1,n+1): dp[i][1] = price[0]*i for i in range(2,n+1): for j in range(2,i+1): dp[i][j] = max(price[j-1]+dp[i-j][i-j],dp[i][j-1] ) print(dp[n][n]) 이번 문제는 구매하려고 하는 카드의 개수 N과 각 개수마다 구매하는데 필요한 비용 P1 ~ PN 까지 주어졌을 때, 카드 N개를 최대한 많은 비용으로 구매하였을 때의 금액을 구하는 문제이다. 이 문제를 풀 때 문득 '0-1 배낭 문제'가 떠올랐는데, 비슷한 느낌..

def dynamic(data): n = data[0] m = data[1] dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1,n+1): dp[i][i] = 1 for i in range(2,m+1): dp[1][i] = i for i in range(2, n+1): for j in range(i+1,m+1): dp[i][j] = dp[i-1][j-1] + dp[i][j-1] print(dp[n][m]) t = int(input()) testcase = [] for i in range(t): testcase.append(list(map(int,input().split()))) for i in testcase: dynamic(i) 이번 문제는 서쪽 사이트의 개..

n = int(input()) array = list(map(int,input().split())) if n == 1: print(array[0]) else: dp = [0]*n dp[0] = array[0] for i in range(1,n): dp[i] = max(array[i],dp[i-1] + array[i]) print(max(dp)) 이번 문제는 주어진 수열에서 연속된 수열 중 가장 합이 큰 수열의 합을 구하는 문제이다. 처음에는 어떻게 경우의 수를 구해야할지 고민했었는데 곰곰히 생각해보니 첫번째 수부터 연속된 수열을 찾는 경우, 결국에는 마지막 수까지 고려를 해야한다는 것을 깨닫고 DP 알고리즘을 사용하여 첫번째 수부터 시작해서 최적의 값을 DP 테이블에 저장해가는 방식으로 풀어보기로 했다...

# 1 # 2 # 3 (2 + 1) # 5 (3 + 2) # 8 (5 + 3) # 13 (8 + 5) n = int(input()) if n == 1: print(1) elif n == 2: print(2) else: dp = [0]*(n+1) dp[1], dp[2] = 1, 2 for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]%10007) 이번 문제는 2xn 형태의 직사각형이 주어졌을 때, 2x1과 1x2 타일로 채울 수 있는 경우의 수를 구하는 문제이다. n=1, n=2, n=3 .. 인 경우의 수를 차례대로 구하다보니 dp[n] = dp[n-1] + dp[n-2] 라는 점화식을 도출해낼 수 있어서 쉽게 해결할 수 있었던 문제였다 :)

import sys input = sys.stdin.readline def fibo(n): if n == 0: print(1,0) return None if n == 1: print(0,1) return None dp = [[0]*2 for _ in range(n+1)] dp[0][0], dp[0][1] = 1,0 dp[1][0], dp[1][1] = 0,1 for i in range(2,n+1): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] print(dp[n][0],dp[n][1]) t = int(input()) testcase = [0]*t for i in range(t): testcase[i] = int(input()..

# 1 3 6 10 # 1 2 3 4 def dynamic(data): floor = data[0] index = data[1] dp = [[0] * (index+1) for _ in range(floor+1)] for i in range(1,index+1): dp[0][i] = i for i in range(1,floor+1): for j in range(1, index+1): if j == 1: dp[i][j] = 1 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[floor][index] t = int(input()) data = [[0]*2 for _ in range(t)] for i in range(t): for j in range(2): data[i]..

def dynamic(n): if n == 1: return 1 if n == 2: return 2 if n == 3: return 4 dp = [0]*(n+1) dp[1],dp[2],dp[3] = 1, 2, 4 for i in range(4, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] return dp[n] t = int(input()) result = [] for i in range(t): n = int(input()) result.append(dynamic(n)) for i in result: print(i) 이번 문제는 주어진 정수 N을 1, 2, 3의 합으로 만들 수 있는 경우의 수를 구하는 문제이다. n=1, n=2, n=3 인 경우를 DP 테이블에 저장하고 n..