흙금이네 블로그

아이디어 원생들의 키 차이를 정렬하여 차이가 큰 값들을 제외하고 나머지 합을 구한다. 차이가 큰 값들은 어디에 포함되더라도 비용에 포함되므로 경계를 나눠 분리해야 비용을 줄일 수 있다. 풀이 원생들의 키 차이를 리스트 D에 추가하여 정렬한 후, K-1개의 큰 값들을 제외한 나머지 값들의 합을 구해 출력한다. 리스트 D의 길이는 N-1이므로 뒤에서부터 K-1개의 값을 제외하려면 D[:N-K]를 사용하면 된다. N, K = map(int, input().split()) H = list(map(int, input().split())) D = [] for i in range(N-1): D.append(H[i+1]-H[i]) D.sort() print(sum(D[:N-K])) 리스트 컴프리헨션보다 for문에서 a..

아이디어 현재 공보다 크기가 작은 공들의 크기 합과 크기가 작으면서 색이 같은 공들의 크기 합을 구하여 풀 수 있다. 풀이 공을 저장하는 리스트 balls에 공의 크기, 공의 색, 인덱스를 순서대로 추가하고 공의 크기 오름차순으로 정렬한다. 차례로 현재 공보다 작은 공의 크기를 total에 누적하여 더하고, sum_color 리스트에 공의 색에 따라 누적하여 더한다. 작은 공들의 크기 합에서 작으면서 색이 같은 공들의 크기 합을 뺀 값을 인덱스에 맞게 결과값으로 저장한다. import sys input = sys.stdin.readline N = int(input()) balls = [] for i in range(N): a, b = map(int, input().split()) balls.append(..

아이디어 도킹할 수 있는 가장 큰 번호의 게이트에 비행기를 도킹한다. 풀이 자신의 루트 노드를 가리키는 group 리스트를 만들고 유니온 파인드로 루트 노드보다 하나 작은 노드를 할당해 나간다. 루트 노드 번호가 0인 경우 더 이상 남은 게이트가 존재하지 않으므로 결과값을 저장하고 종료한다. sys.stdin.readline으로 입력을 받고 유니온 파인드 경로를 압축해주어야 시간 초과가 나지 않는다. import sys input = sys.stdin.readline G = int(input()) P = int(input()) group = [i for i in range(G+1)] res = P for i in range(P): g = int(input()) idx = g while group[idx]..

아이디어 노드를 지운 후 BFS로 자식이 없는 리프 노드의 개수를 센다. 풀이 2차원 리스트 tree에 지울 노드를 제외한 나머지 자식 노드의 번호를 자신의 부모 노드 인덱스에 맞춰 추가한다. BFS로 자식이 없는 리프 노드의 개수를 세어 결과값으로 출력한다. 지울 노드는 tree에 추가하지 않았으므로 탐색하지 않고 BFS가 종료된다. N = int(input()) tree = [[] for _ in range(N)] P = map(int, input().split()) r = int(input()) li = [] for idx, n in enumerate(P): if idx != r: if n >= 0: tree[n].append(idx) else: li.append(idx) res = 0 while ..

아이디어 두 물병을 하나로 합치기 위해서는 두 물병의 물 양이 같아야 한다. N이 0보다 크거나 같은 범위에서 가장 큰 2의 거듭제곱으로 계속해서 빼나가고, K 번째 이후에 남은 물을 K 번째 물병에 합치기 위해 필요한 물의 양을 계산한다. 풀이 N에서 뺄 수 있는 가장 큰 2의 거듭제곱 n을 K번 동안 뺀다. 만약 K번 이내에 N이 0이 된다면 물병이 추가로 필요하지 않으므로 0을 출력하고 종료한다. K 번째 물병까지 모두 채웠다면 마지막 K 번째 물병의 물 양 n에서 남은 물 양 N을 뺀 값을 출력한다. 정답은 항상 존재하므로 -1을 출력하는 경우는 없다. N, K = map(int, input().split()) n = 1 while n < N: n *= 2 for i in range(K): whi..

아이디어 #1 DP로 가장 긴 공통 부분 문자열의 길이를 찾는다. 풀이 #1 2차원 리스트 dp를 생성하고 두 문자열의 문자를 차례로 비교한다. 두 문자가 같다면 이전 공통 부분 문자열의 길이보다 1 증가시킨 값을 저장하고 결과값을 갱신해 나간다. Python3로 제출했을 때 시간 초과가 났으며, PyPy3로 제출하여 통과할 수 있었다. S1, S2 = input(), input() N1, N2 = len(S1)+1, len(S2)+1 dp = [[0]*N2 for _ in range(N1)] res = 0 for i in range(1, N1): for j in range(1, N2): if S1[i-1] == S2[j-1]: dp[i][j] = dp[i-1][j-1]+1 res = max(res, d..

아이디어 벌통이 두 벌들보다 왼쪽이나 오른쪽에 있는 경우는 벌 한 마리와 벌통을 양쪽 끝에 배치하는 것이, 벌통이 두 벌들 사이에 있는 경우는 벌 두 마리를 양쪽 끝에 배치하는 것이 가장 많은 꿀을 딸 수 있다. 전자는 나머지 벌 한 마리의 위치를 조정하면서 최댓값을 찾고, 후자는 벌통의 위치를 조정하면서 최댓값을 찾는다. 풀이 벌들이 왼쪽에서 출발하는 누적합과 오른쪽에서 출발하는 누적합을 각각 left와 right 리스트에 저장한다. 결과값을 벌통이 두 벌들 가운데 있는 경우의 최댓값으로 초기화한다. 차례로 남은 벌의 위치를 조정하여 현재 최댓값과 출발 위치에 따른 두 값들을 비교해 결과값을 갱신해 나간다. N = int(input()) honey = list(map(int, input().split(..

ECMAScript5(ES5)에서는 새로운 기능이 추가되고 기존 기능 중 일부가 변경되었다. 이에 따른 하위 호환성 문제가 발생하지 않도록 변경사항 대부분은 ES5 기본 모드에서 활성화되지 않고, use strict라는 지시자를 사용하여 엄격 모드를 활성화했을 때만 활성화되도록 설계되었다. use strict는 함수 본문 맨 앞에 올 수도 있으나 대개 스크립트 최상단에 위치한다. 스크립트 최상단에 위치하지 않으면(주석 제외) 엄격 모드가 활성화되지 않을 수도 있으므로 주의해야 한다. 'use strict'; use strict를 사용하여 적용된 엄격 모드를 취소할 수는 없다. 모던 자바스크립트의 클래스와 모듈은 use strict가 자동으로 적용된다. 따라서 클래스와 모듈을 사용한다면 use strict..

아이디어 라운드를 돌면서 현재 라운드까지 적이 많이 등장했던 라운드들에서 무적권을 사용한다. 입력 값의 범위가 크므로 힙을 이용하며, 힙에서 최솟값을 삭제하고 큰 값들을 저장하기 위해 최소힙으로 구현한다. 풀이 swap 함수는 배열을 이용하여 두 노드가 서로의 값을 참조하도록 하여 값을 바꾸도록 한다. heappush 함수는 힙에 노드를 삽입하고, 차례로 부모 노드와 값을 비교하여 최소힙으로 정렬한다. heappop 함수는 힙의 최솟값인 루트 노드를 힙의 마지막 노드와 자리를 바꾼 뒤 그 값(없으면 0)을 저장해두고 삭제한다. 루트 노드에서부터 차례로 자식 노드들과 값을 비교하여 두 자식 노드 중 값이 가장 작은 노드와 자리를 바꿔 정렬한다. 라운드를 돌면서 힙에 큰 값들이 저장되도록 갱신해 나가고, 그..

아이디어 #1 DFS로 탐색해 나가다 현재 탐색에서 사이클이 발견되는 경우 해당 사이클에 포함되는 노드들 수를 결과값에서 뺀다. 풀이 #1 결과값을 노드 개수로 초기화하고, 차례로 방문하지 않은 노드들로부터 DFS를 시작한다. 지나온 노드들을 path 리스트에 저장하고 그 인덱스를 idx_dict 딕셔너리에 저장한다. 다음에 방문할 노드가 이미 path 리스트에 존재하는 경우 해당 노드를 포함하여 이후 노드들의 개수를 결과값에서 뺀다. path 리스트에 존재하지는 않지만 이미 방문한 노드인 경우 현재 탐색을 종료한다. import sys input = sys.stdin.readline T = int(input()) for t in range(T): N = int(input()) graph = [0]+li..