어흥

문제 링크: https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 1. 주의할 점 - 트리 탐색시 방문 검사를 하지 않으면 TLE가 날 수 있다 2. 구현 - 간선에 대한 정보를 Li[] 배열에 담는다 - Root부터 idx Node까지의 거리를 Dist[idx]에 저장한다 - 트리 탐색을 하며, Leaf Node인 경우, Sum에 Dist[] 값을 추가한다 - 성원이가 게임을 이기기 위해서는 홀수번째 움직임에 게임이 끝나야 한다. 즉, Leaf N..

문제 링크: https://www.acmicpc.net/problem/22867 22867번: 종점 주행을 마친 버스들이 종점에 들어온다. 종점에 들어온 버스는 버스를 정비하기 위한 자리에 들어간다. 즉, 종점에 버스 4대가 있다면 버스를 정비할 수 있는 공간이 최소 4개 이상 필요하다. www.acmicpc.net 1. 주의할 점 - 정렬 방법을 잘 수립한다 - 우선순위 큐를 사용한다 - 초기에 구상했던 정렬에 대한 반례는 아래에 있습니다 (PQ 1개만 이용) 더보기 #TC 1 3 00:00:00.000 00:00:00.002 00:00:00.000 00:00:00.010 00:00:00.002 00:00:00.010 AC: 2 #TC 2 6 00:00:00.000 00:00:00.002 00:00:0..

문제 링크: https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 1. 주의할 점 - 우선 순위큐에 사용될 정렬 방법을 잘 정리한다 - 사람수 < 카운터 수 일 때? 2. 구현 - Cmp 비교함수를 통해 우선순위큐의 정렬 방법을 정리한다 - Counter의 수만큼 enterCounter 우선순위큐에 미리 삽입한다 (id는 0으로 설정. 이유는 하단에..) - id와 물건의 수 w를 입력받고, enterCounter의 ..

문제 링크: https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 주의할 점 - 분리집합 알고리즘에 대해 알고 있어야 한다 2. 구현 - findPar() 함수를 통해 해당 Node의 부모를 반환하는 함수를 구현한다 - makeUnion() 함수를 통해 a와 b의 최상위 부모를 연결한다 - M개의 선분을 입력받으면서 해당 선분의 부모가 같지 않으면 makeUnion()을 통해 같게 해준다. 만약 같고 finish 값이 0이 아니라면 fin..

문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 1. 주의할 점 - 홀수번째마다 정렬해서 중앙값을 구하지 않는다 2. 구현 - 2가지의 우선순위 큐를 사용한다(오름차순 정렬, 내림차순 정렬 각각 1개씩) - 중앙값을 기준으로 왼쪽에는 내림차순으로 정렬된 Left 우선순위큐를, 오른쪽에는 오름차순으로 정렬된 Right 우선순위큐가 있다고 가정한다 - 홀수번째마다 Right와 Left의 크기를 비교하며 만약..

문제 링크: https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. 주의할 점 - Int의 범위를 벗어날 수 있다 2. 구현 - 우선순위큐를 사용한다. 이때, 오름차순 정렬을 적용시킨다 - 값이 가장 낮은 2개를 더하는 것이 최소의 값을 가지므로 우선순위큐의 앞 2개 원소를 빼서 더하고 추가한다 #include #include #include using namespace std; int main() { ios..

문제 링크: https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 주의할 점 - TLE가 나지 않도록 한다 2. 구현 - 덱이나 우선순위큐를 사용하여 해결한다 - 모든 원소를 입력받을 때, 삽입을 수행한다 - 우선순위 큐의 크기가 Len만큼 길지 않다면, 출력만 수행한다 - 우선순위 큐의 크기가 Len보다 크거다 같다면, While문을 통해 우선순위큐에서 제거작업을 수행한다. 이때, Top에 존재하는 원소가 현재..

문제 링크: https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 주의할 점 - 연속된 부분의 누적 합에 대해 알고 있어야 한다 - O(N^2)보다 작은 알고리즘을 구현해야 한다 - 답이 int 범위를 벗어날 수 있다 2. 구현 - 나머지가 M으로 나눠떨어지는 누적합은 2가지의 방식이 존재한다(파란 글씨 + 빨간 글씨) - 값을 입력받으며, Sum[] 함수에 연속된 누적합을 M으로 나눈 값을 저장..