흙금이네 블로그

아이디어 동적 계획법으로 각 블록을 사용하여 탑을 만드는 경우의 수를 구해 나간다. 풀이 #1 (Python) 2624번 동전 바꿔주기 문제 풀이와 유사하다. 0으로 채워진 H+1 크기의 리스트 dp를 생성하는데, dp[i]에는 높이 i의 탑을 만드는 경우의 수를 저장한다. for문에서 리스트 blocks에 블록들의 높이를 입력 받고, temp에 리스트 dp를 복사하여 저장한다. blocks의 블록 하나로 해당 블록의 높이만큼 탑을 쌓는 경우의 수 dp[b]를 1 증가시키고, 해당 블록을 기존 블록들을 함께 사용해 탑을 쌓아 높이 i의 탑을 경우의 수를 temp[i-b]만큼 증가시킨다. 높이 H의 탑을 쌓는 경우의 수를 10,007로 나눈 나머지를 출력한다. import sys input = sys.st..

아이디어 동적 계획법으로 각 동전을 사용한 교환 방법의 가짓수를 저장해 나간다. 풀이 #1 (Python) 0으로 채워진 T+1 크기의 리스트 dp를 생성하는데, dp[i]에는 i원의 교환 방법 가짓수를 저장한다. for문에서 동전의 금액 p와 동전 개수 n을 입력 받고, temp에 리스트 dp를 복사하여 저장한다. p원 동전으로만 교환하는 방법의 가짓수는 1이므로 n 이하의 자연수 i에 대해 dp[p*i]를 1씩 증가시킨다. p원 동전을 사용하여 교환하는 방법의 수는 그 금액보다 p원만큼 작은 금액을 기존 동전들로 교환하는 방법의 수와 같다. 따라서 기존 동전들과 함께 사용하여 교환하는 방법의 수 dp[j]에 기존 동전들로만 교환하는 방법의 수 dp[j-p*i]를 더한다. 지폐의 금액 T를 넘는 동전의..

아이디어 동적 계획법으로 감소하는 수열 합의 최댓값을 구한다. 풀이 #1 (Python) 리스트 dp에 수열 A와 같은 값들을 저장한다. 이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다. max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다. def solution(): N = int(input()) A = tuple(map(int, input().split())) dp = list(A) for i in range(N): for j in range(i+1, N): if A[j] dp[j]: dp[j] = dp[i]+A[j] print(max(dp)) solution() 풀이 #2 (Jav..