부분합3 [leetcode] 1094. Car Pooling 문제 : https://leetcode.com/problems/car-pooling/ 총 좌석이 capacity인 차량이 있다. 차량엔 capacity 만큼의 탑승자만 태울 수 있다. 차량은 동쪽으로만 주행하며 (탑승자 수, from, to) 정보를 저장한 trip 배열이 주어진다. from에서 탑승자 수 만큼 차량에 태우고 to에 탑승자 수 만큼 차량에서 내린다. capacity를 넘지 않게 모든 trip 여행들을 탐색할 수 있으면 true 아니면 false를 반환하라. 부분합 배열을 만들어서 풀 수 있다. to의 최대값이 1000이므로 1000 크기의 passenger 배열을 만든다. trips 배열을 탐색하며 passenger[from] 에는 탑승자 수 만큼 더하고, passenger[to]에는 탑.. 2022. 1. 7. [Kickstart][2019]2. Mural 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/0000000000058b89 부분합으로 풀었다.벽은 가장자리부터 파괴되고 벽의 총 N개라고 했을 때 최대 (N+1)/2 개의 벽을 칠할 수 있다.즉, 문제를 간단하게 보면 연속되는 (N+1)/2개의 벽을 선택할 때 구할 수 있는 최대 값을 구하는 문제이다.부분합 배열을 sum, (N+1)/2를 cnt라고 했을 때, sum[i] - sum[i-cnt]가 (N+1)/2개의 벽을 선택했을 때의 가치이고. i 범위가 [cnt, N] 일 때 구한 가치 중 최대 값이 정답이 된다.시간 복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns.. 2019. 2. 25. [BOJ][2003] 수들의 합 2 문제 : https://www.acmicpc.net/problem/2003 부분합 + 투포인터 로 풀었다. N개의 수를 입력받으면서 부분합 배열을 만든다.subSum[i] = i까지 수들의 합. 인덱스 변수 2개를 준비한다. (l, r)2개의 변수는 부분합의 범위를 구하는데 사용되며 범위는 (l, r] 이다.범위가 (l, r] 일 때 해당 부분 배열의 합은 subSum[r] - subSum[l] 이 된다. l, r을 0에서부터 증가시키면서 해당 부분 배열의 합이 M과 같다면 정답이 될 수 있는 경우이다.합이 M보다 작다면 부분 배열의 합이 더 커져야 하므로 r을 증가시키고M보다 크다면 합이 더 작아져야 하므로 l을 증가시킨다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com.. 2019. 2. 16. 이전 1 다음