흙금이네 블로그

아이디어 동적 계획법으로 어떤 객차까지의 객차들 중에서 최대로 운송할 수 있는 손님 수를 구해 나간다. 풀이 전체 객차 수를 N, 소형 기관차 한 대가 끌 수 있는 최대 객차 수를 M에 저장한다. 객차 손님 수는 앞에 0을 추가하여 리스트 acc에 저장하고, acc를 누적합 리스트로 만든다. 0으로 채워진 4*(N+1) 크기의 2차원 리스트 dp를 만들고, for문으로 진입한다. dp[i][j]는 i 번째 소형 기관차가 j 번째 객차까지의 손님들 중 운송할 수 있는 최대 손님 수를 나타낸다. 그 다음 순번의 소형 기관차는 이전 순번의 소형 기관차가 운송하는 손님과 겹치지 않도록 M만큼씩 차이를 둔다. def solution(): N = int(input()) acc = [0]+list(map(int, i..

아이디어 W을 구성하는 문자들의 인덱스를 문자별로 저장해 인덱스 값의 차이로 문자열 길이를 구한다. 풀이 #1 (Python) W를 구성하는 알파벳 소문자의 인덱스를 저장하기 위한 2차원 리스트 alpha를 만든다. for문에서 함수 ord를 사용하여 W의 a부터 z를 0부터 25에 매칭해 alpha에 문자별로 W에서의 인덱스를 저장한다. 이후 alpha에서 문자별로 K개의 문자를 포함하는 문자열의 길이를 리스트 res에 추가해 나간다. res에 값이 존재하면 res에서의 최솟값과 최댓값을 출력하고, 존재하지 않으면 -1을 출력한다. import sys input = sys.stdin.readline def solution(): T = int(input()) for t in range(T): alpha ..

아이디어 위쪽, 왼쪽, 오른쪽의 가능한 지역 중 최대 가치를 더해 나간다. 풀이 입력 받은 N, M을 저장하고, 첫 행을 입력 받아 리스트 dp에 저장한다. 첫 행의 지역들은 시작 지점을 제외하고는 왼쪽 지역을 탐사해야 이동할 수 있으므로, dp를 오른쪽으로 누적하여 더한다. 첫 행과 마지막 행의 지역들을 제외한 지역들을 처리하기 위해 N-2의 크기로 for문을 실행한다(N > 2일 때 실행). 우선 현재 행을 arr에 입력 받고, arr과 같은 크기로 0이 채워진 리스트 temp를 생성한다. temp에는 왼쪽에서 오른쪽으로 탐사해 나갈 때의 최대 가치를 저장한다. temp의 첫 번째 값은 arr의 첫 번째 값(현재 지역 가치)과 dp의 첫 번째 값(위쪽 지역 최대 누적 가치)의 합으로 저장하고, 나머지..