흙금이네 블로그

아이디어 동적 계획법으로 중간 계산 결과가 0 이상 20 이하인 값들에 대한 경우의 수를 구해 나간다. 풀이 숫자의 개수를 N, 주어지는 숫자를 리스트 numbers에 입력 받는다. 0으로 채워진 (N-1)×21 크기의 2차원 리스트 dp를 생성하는데, dp[i][j]에는 i 번째 중간 계산 결과 j의 경우의 수를 저장한다. 처음 dp[0]의 첫 숫자의 위치에 1을 저장하고, for문에서 0 이상 20 이하의 중간 결과값의 경우의 수를 dp에 저장해 나간다. 마지막 계산 결과값이 주어진 마지막 숫자로 올바른 등식의 수 dp[-1][numbers[-1]]을 출력한다. def solution(): N = int(input()) numbers = tuple(map(int, input().split())) dp..

아이디어 세그먼트 트리로 구간 합을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 1275번 커피숍2 문제 풀이와 유사하다. 구간 합을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 0으로 채워진 트리 리스트 tree를 만든다. for문에서 a가 0이 아닌 경우(1인 경우) 해당 트리 리프 노드의 수를 변경한 후 함수 modify를 호출하고, a가 0인 경우 구간 합을 구하는 함수 sum_up을 호출하는데, b가 c보다 더 크다면 b와 c를 바꿔 c에 더 큰 값이 오도록 한다. 함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 루트 노드를 벗어나면 종료한다. 함수 sum_up에서는 리프 노드에서부터 차례로 해당 노드의 부모 노드..

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 고객 수에 필요한 최소 비용을 저장하는 C+1 크기의 리스트 dp를 생성하고, 초기값을 비용 최댓값 100,000으로 채운다. for문에서 홍보 비용과 그 고객 수를 a와 b에 입력 받고, 고객 i명을 얻는 데 필요한 최소 비용 dp[i]를 갱신해 나간다. b의 배수 이하의 고객을 얻는 비용을 그에 맞는 a의 배수와 비교해 더 작은 값으로 갱신한다. 또 고객 수 i에서 b만큼의 고객을 홍보 비용 a로 얻었을 때의 비용인 dp[i-b]+a와 비교해 더 작은 값으로 갱신한다. import sys input = sys.stdin.readline def solution(): C, N = map(int, input().sp..