시간 제한 - 1s 메모리 제한 - 256MB 풀이 1. 부분 수열의 합 / 부분 수열의 길이 = 해당 부분 수열의 평균임을 이용해 풀이 (N까지의 누적합 / N = 평균) 2. (N까지의 누적 합 - x까지의 누적 합) / (N - x) = x부터 N까지의 평균 인덱스 0 1 2 3 4 5 6 배열 1 1 1 1 1 1 누적합 0 1 2 3 4 5 6 평균 0 1 1 1 1 1 1 위 테이블에서 6까지의 평균은 당연히 1이다. 만일 찾으려는 값이 1이라면, 이를 만족하는 구간은 모든 구간인 N * (N + 1) / 2인 21이 나와야 함(1:1, 1:2, 1:3, 1:4, 1:5, 1:6, 2:2, 2:3 ••• 6:6) 3. 누적합을 구하고 평균을 계산해 해당 값이 나온 횟수를 구해준다. 4. 평균을..

당신이 만약 백준 플래티넘 티어에 도전하는 모험가라면 부스터 한개는 남겨놓았길 바란다. 최소 골드 2부터 시작하는 쉽지 않은 알고리즘임에도 불구, 트리를 초기화 및 업데이트하고 누적합만 구하는 accumulator가 된다면, 골1 수문장은 쉽게 돌파할 수 있을 것이기 때문이죠. 세그먼트 트리는 데이터 배열에서 특정 범위에 대한 쿼리를 효율적으로 수행하는 균형 잡힌 이진트리 형태의 자료구조로 트리의 리프 노드는 전체 배열의 단일 요소를 표현하며, 트리 내부의 각 노드는 요소의 범위를 나타냅니다. 트리의 각 내부 노드는 상위 노드가 표현하는 범위의 왼쪽과 오른쪽을 절반씩 나타내는 두 개의 하위 노드를 가지며, 상대적으로 적은 수의 노드로 어레이의 전체 범위를 나타낼 수 있으며 범위 값의 수정과 검색에 있어 ..

시간 제한 - 2s 메모리 제한 - 256MB 풀이 1. 최단경로가 최대가 되기 위해서는 최단경로를 끊어야한다. 최단경로가 아닌 간선을 끊어봐야 최단경로는 그대로이기 때문 2. 최단경로를 구해, 해당 경로에서 거치는 노드를 하나씩 끊고, 다시 최단경로를 구하는 방식으로 최대 값을 구한다. 3. 최단 경로가 여러 개일 때, 현재의 최단 경로만 확인하는게 의미가 있는지? 3.1) 동일한 최단경로가 없을 때(A->B) - A->B가 최단경로이므로, A->B를 끊으면 A->C->B로 최단경로가 1 늘어나며 A-C, C->B 등 최단경로 이외의 간선을 끊어도 결과는 A->B로 같은 걸 확인할 수 있음 3.2) 동일한 최단 경로가 중복되지 않는 경로로 존재할 때(A->G) - A->B->D->G 또는 A->C->E..

시간 제한 - 1s 메모리 제한 - 128MB 풀이 1. 구슬과 추를 활용해 무게를 재는 방법 1.1) 그림 1을 식으로 나타내면 구슬 + 추a + 추b == 추x + 추y ?로 표현 가능 1.2) 그림 2를 식으로 나타내면 구슬 == 추x + 추y ?로 표현 가능 -> 방정식의 성질을 이용해 1.1의 식을 구슬 == 추x + 추y - 추a - 추b와 같이 나타냄으로 두 식을 같게 생각할 수 있음 2. 1번의 추1부터 추n까지의 조합을 이용해 만들 수 있는 무게 중 구슬의 무게가 있으면 비교 가능하다고 판단 가능 입력 추의 수 N, N개의 추 구슬의 수 M M개의 구슬 자료구조 dp 테이블을 만들까했지만 추를 이용해 만들 수 있는 무게의 집합을 표현하기에 set 자료구조가 좋다고 판단함 추n-1개의 se..

시간 제한 - 2s 메모리 제한 - 512MB 풀이 n일차와 n-1일차를 모두 비교해 n, n-1, n-2 .. 1일까지의 최대 값을 모두 비교하면서 그날 그날의 최대 값에 상담을 통해 n + t일의 최대 값을 누적해줌 배열로 전부 받고 탑다운으로 들어가도 되지만 메모리를 절약할 수 있다고 생각해서 배열 없이 입력 받으면서 동시에 처리해줌 입력 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) 입력 값이 150만이라 입력 스트림을 튜닝안하면 바로 터짐 자료구조 n일 간의 최대 값을 담기 위한 int형 배열 로직 1. i째 날에 벌 수..

시간 제한 - 10s 메모리 제한 - 256MB 풀이 기본적인 개념은 잠금해제를 하지 않고 사용할 수 있는 컴퓨터를 pool로 관리한다는 개념에서 시작 컴퓨터의 사용 종료와 종료 후 락이 걸리는 시간을 오름차순으로 관리한다. 이미 락이 걸린 컴퓨터는 항상 다시 잠금을 해제해야하기 때문에 연구원의 입실 시간을 기준으로 이미 락이 걸린 컴퓨터는 전부 관리 목록에서 제거해준다. 만약 종료가 된 이후의 컴퓨터이고 연구원의 시작시간이 락이 걸리기 전이라면 해당 컴퓨터는 잠금을 다시 해제하지 않고 절약할 수 있다. 입력 연구원의 수 n과 사용 종료 후 잠금이 걸리는 시간까지의 길이 m이 입력되고 연구원의 입실과 입실 이후 사용 시간이 n회 입력된다. 자료구조 연구원의 입장 시간과 사용 시간을 입력받을 형 배열 먼저..