Python/Coding Test

11411 합 구하기

문제 https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 접근 주어진 수의 개수 n과 구간의 수 m의 범위가 1

13702 이상한 술집

문제 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 접근 막걸리 주전자의 개수(s개)가 나누어줄 사람(c개)보다 작거나 같고, 정해진 용량을 나누어주고 남은 막걸리는 버린다고 했으므로, 나누어줄 수 있는 막걸리의 최댓값을 결정할 수 있다. 0과 최댓값 사이에서 문제의 제한조건을 만족시키는 경우를 찾아 나서면 되므로, 이분탐색으로 풀이 풀이 lt를 1로, rt를 주전자에 들어있는 막걸리의 최솟값으로 설정 mid 값에 대해서 각 주전자마다 몇 명에..

2110 공유기 설치

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 주어진 집들(n개)에 공유기(c개)를 설치할 때, 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제 가장 처음 든 생각은 집들 중 공유기를 설치할 집들을 선택하는 방법으로 접근하려 했으나, 이 방법의 시간 복잡도는 nCc이며, n과 c의 범위가 2 ≤ n ≤ 200,000, 2 ≤ c ≤ n 이므로 시간초과가 날 것 (제한시간 2..