흙금이네 블로그

아이디어 동적 계획법으로 중간 계산 결과가 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..

아이디어 덱을 이용하여 범위 내에서의 최솟값을 찾는다. 풀이 for문에서 현재 값이 덱 queue에서 가장 작은 값이 되도록 현재 값보다 큰 값들은 pop하여 없앤다. 범위를 벗어나는 값들은 popleft로 제거하는데, pop하여 남아 있지 않은 값이 있을 수 있으므로 A의 해당 값과 비교한다. res에 queue의 맨 앞에 있는 값을 문자열로 추가한 후, join 메서드로 공백으로 구분한 결과값을 출력한다. from collections import deque def solution(): N, L = map(int, input().split()) A = tuple(map(int, input().split())) queue = deque() res = [] for i in range(N): while q..

아이디어 동적 계획법으로 각 상담이 끝나는 시점의 최대 수익을 갱신해 나간다. 풀이 #1 (Python) N+1 크기의 0으로 채워진 리스트 dp를 생성하는데, dp[i]에는 i일째의 최대 수익을 저장한다. for문에서 T와 P를 입력 받아 어제 수익 dp[i]가 오늘 수익 dp[i+1]보다 큰 경우 오늘 수익에 어제 수익을 저장한다. 이번 상담이 끝나는 T-1일 후가 퇴사 전이고, 상담으로 얻는 수익이 T-1일 후의 예정 수익보다 더 크면 값을 갱신한다. import sys input = sys.stdin.readline def solution(): N = int(input()) dp = [0]*(N+1) for i in range(N): T, P = map(int, input().split()) if..

아이디어 세그먼트 트리로 구간 합을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 2042번 구간 합 구하기 문제와 유사하다. 구간 합을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 0으로 채워진 트리 리스트 tree를 만든다. 트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 합을 저장한다. 이후 for문에서 x~y의 구간 합을 구하는 함수 sum_up을 호출하여 그 반환값을 출력하고, a의 위치에 해당하는 트리 리프 노드의 수를 변경한 후 함수 update를 호출한다. 이때 y에 더 큰 값이 오도록 x가 y보다 더 크다면 x와 y의 값을 서로 바꾼다. 함수 update에서는 while문을 반복하며 리프..

아이디어 동적 계획법을 이용해 각 칸에서 이동할 수 있는 칸의 경우의 수를 증가시켜 나간다. 풀이 #1 (Python) 게임판의 수를 2차원 리스트 board에 저장하고, 이동 경로의 수를 저장하는 0으로 채워진 2차원 리스트 dp를 생성한다. board의 가장 오른쪽 아래 칸과 dp의 가장 왼쪽 위 칸에 각각 1을 저장한다. board의 가장 오른쪽 아래 칸 값을 1로 바꿔 해당 칸 dp에 해당 칸 경로의 수를 더하는 것을 막는다. 이중 for문에서 현재 칸 (i, j)에서 이동할 수 있는 칸 (i+board[i][j], j)와 (i, j+board[i][j])의 dp에 현재 칸 경로의 수를 더한다. import sys input = sys.stdin.readline def solution(): N =..

아이디어 누적합으로 S에서 홀수 원소들을 최대 K번 삭제한 연속된 짝수 수열의 길이를 구한다. 풀이 22857번 가장 긴 짝수 연속한 부분 수열 (small)의 풀이 #2와 같다. 리스트 arr에는 홀수 원소로 구분된 짝수로 이루어진 수열의 길이를 누적합으로 저장한다. for문에서 S의 각 원소가 홀수면 리스트 arr에 arr의 마지막 값을 다시 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. arr의 K 번째 원소까지는 앞의 홀수 원소들을 모두 제거할 수 있으므로 그 마지막 값을 결과값 res에 저장한다. for문에서 K개의 홀수 원소를 제거한 짝수로 이루어진 수열 길이의 최댓값으로 res를 갱신해 나간다. arr의 길이 M이 K보다 작다면 결과값 res에는 누적합의 최댓값이 저장되고, for문..

아이디어 S의 홀수 원소로 구분된 연속된 짝수 수열의 길이를 구한 후 그 길이의 합의 최댓값을 찾는다. 풀이 #1 (Python) 리스트 arr의 초기값으로 0을 넣어두고 S의 각 원소가 홀수면 arr에 0을 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. 따라서 arr에는 짝수로 이루어진 수열의 길이가 홀수 원소로 구분되어 저장되고, 연속된 arr 원소들의 합은 그 원소 수만큼 S에서 홀수 원소를 삭제한 짝수로 이루어진 수열의 길이와 같다. arr을 복제해 리스트 dp에 저장하고, for문에서 앞의 홀수 원소를 반복 횟수만큼 삭제한 수열의 길이로 dp를 갱신해 나간다. 같은 for문 내에서 구한 값이 현재 결과에 영향을 미치지 않도록 dp의 원소들을 역순으로 갱신한다. def solution()..

아이디어 스택을 이용하여 각 위치에서 해당 직사각형의 높이로 만들 수 있는 가장 큰 직사각형 넓이를 구해 나간다. 풀이 6549번 히스토그램에서 가장 큰 직사각형에서 스택을 이용한 풀이 #2와 같다. 첫 번째 수는 N, 직사각형의 높이들은 sys.stdin.readlines로 H에 입력 받고, H 끝에는 0을 추가한다. 직사각형의 넓이를 구하기 위해 필요한 직사각형의 위치들을 스택 stack에 저장하고, 이 위치로 직사각형 양쪽 끝과 H에서 해당 직사각형의 높이를 알 수 있어 각 위치에서의 직사각형의 면적을 구할 수 있다. for문에서는 차례로 직사각형 높이가 증가하면 그 위치를 스택에 넣고 감소하면 스택에서 위치를 꺼내 그 넓이를 계산한다. 위치 i의 직사각형 높이가 stack[-1] 위치의 직사각형 ..