나그네

29160번: 나의 FIFA 팀 가치는? 문제 https://www.acmicpc.net/problem/29160 29160번: 나의 FIFA 팀 가치는? 첫 번째 줄에 선수의 수 $N$과 $K$가 공백으로 구분되어 주어진다. $(0\leq N\leq 1\,000\,000;$ $1\leq K\leq 50\,000)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $i$번째 선수의 포지션 $P_{i}$, 선수 가치 $W_{i}$가 www.acmicpc.net 풀이 항상 가치가 가장 높은 선수를 선발하는 과정을 반복하기 때문에 우선순위 큐(최대 힙)를 사용한다. 11개의 포지션 번호별로 선수를 저장할 수 있는 우선순위 큐 배열을 만든다. 각각의 포지션 번호별로 비어있는 우선순위 큐를 제외하고 한 명씩 선수를..

28703번: Double It 문제 https://www.acmicpc.net/problem/28703 28703번: Double It $31$에 $2$를 곱해서 $62$로, $41$에 $2$를 곱해서 $82$로, $51$ 에 $2$를 곱해서 $102$로, $3$에 $2$를 $5$번 곱해서 $96$으로 만들면, $A$의 최댓값 $102$와 최솟값 $62$의 차이가 $40$으로 최소가 됩니다. www.acmicpc.net 풀이 본 대회 때는 삽질만 종일 하다가 결국 못 푼 문제. 에디토리얼 참고해서 풀었다. 배열의 최솟값을 두배로 증가시켜 가며 최댓값과의 차를 최솟값으로 비교하며 업데이트한다. 이를 최솟값이 처음 배열의 최댓값보다 작을 때만 계속해서 반복한다. 최솟값 관리를 우선순위 큐로 하면 된다. 코..

1766번: 문제집 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘에 추가적인 정렬 기준이 추가된 문제다. 기본적으로 일반적인 위상정렬과 같이 indegree 배열의 값이 0인 것들을 큐에 넣는데, 가능한 쉬운(번호가 작은) 문제부터 풀어야 하므로 큐 대신 최소 힙을 사용한다. STL에서 우선순위 큐..

1854번: K번째 최단경로 찾기 문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 풀이 다익스트라 알고리즘과 우선순위 큐(최대 힙)를 사용해 풀 수 있는 문제다. 시작 지점이 1로 고정되어 다른 모든 정점까지의 거리를 구하는 문제이므로 다익스트라 알고리즘을 쓸 수 있다. 원래 다익스트라 알고리즘은 최단 거리를 저장하는 dist 배열의 값을 비교해 갱신해 나간다. 하지만 이 문제에서는..

13975번: 파일 합치기 3 문제 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 풀이 두 개의 파일을 합치는데 드는 비용은 두 파일의 크기의 합이다. 합친 파일을 다른 파일과 또 합칠 수 있고 하나의 파일을 만들기 위해 필요한 비용의 최솟값을 구하는 문제다. 각 파일의 크기가 최대 10,000이고 파일의 수가 최대 1,000,000 이므로 long long 자료형을 사용해야 한다. 작은 두 파일을 합치면 비용이 적게 들고 그 파일을 합칠..

11003번: 최솟값 찾기 문제 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 풀이 차례대로 수를 입력받아 최소 힙(우선순위 큐)에 추가한다. 가장 작은 숫자가 현재보다 L만큼 이전 범위 안의 수가 아닌 경우, 범위를 벗어나므로 pop 한다. 최솟값이 범위를 만족할 때 top 원소를 출력해 준다. 코드를 줄이고 줄여서 C++ 기준 숏코딩 1등도 했다. (덱을 사용하는 풀이도 있다고 해서 공부한 후에 추가하겠다...

1202번: 보석 도둑 문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 보석의 무게와 가격이 주어지고 가방에 담을 수 있는 최대 무게가 주어진다. 가방은 최대 1개의 보석만 담을 수 있다. 훔칠 수 있는 보석의 가격의 최댓값을 구하는 문제. 먼저 기본적인 틀은 최대 무게가 가방에 담을 수 있는 보석 중에 가격이 가장 큰 보석을 담는 것이다. 당연히 담을 수 있는 무게가 큰 ..

14622번: 소수 게임 문제 https://www.acmicpc.net/problem/14622 14622번: 소수 게임 인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있 www.acmicpc.net 풀이 에라토스테네스의 체로 미리 500만 이하의 소수를 구해놓은 다음, 입력 범위를 주의하며 차례대로 조건에 따라 구현하면 되는 문제다. 입력받은 수에 따라 조건을 나누어보겠다. 1. 이미 등장한 소수인 경우 이미 등장한 소수인 경우엔 자신이 -1000점을 얻는다. 2. 처음 등장하는 소수인 경우 처음 등장한 소수인 경우엔 해당 소수를 방문처리하고 정렬이 오름차순인 우선순위..