본문 바로가기

큐4

[백준 23090번] 난민 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/23090 23090번: 난민 문제의 답을 공백으로 구분하여 \(N\)줄에 걸쳐 출력한다. \(i\)번째 줄에, \(1\)번째 부터 \(i\)번째까지 이주해온 난민들이 정수시설까지 이동하는 거리의 합이 최소가 되도록 하는 정수시설의 \(y\ www.acmicpc.net 백준에서 새로 추가된 문제들을 보다가 모교 프로그래밍 대회에 나왔던 문제길래 한번 풀어 봤습니다. x = 0을 따라서 강이 흐르고 있고, 정화 시설은 강 위에 설치하게 됩니다. 매번 설치된 모든 난민촌에서 정화 시설까지의 거리의 합이 최소가 되는 곳에 정화 시설을 설치하고, 거리가 최소가 되는 곳이 2개 이상 존재하는 경우, y값이 가장 낮은 곳에 설치.. 2021. 10. 12.
[백준 2696번] 중간값 구하기 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 입력받은 n개의 정수 (n은 홀수) 중, 차례로 읽으며 홀수번째 수를 읽을 때마다 그 수까지의 중간값을 출력하는 문제입니다. 가장 먼저 떠오른 생각은... 매 홀수번째 수를 읽을 때마다, 지금까지 읽은 수를 정렬한 후 중간값을 읽자... 인데 그러면 원소의 개수가 n개라면 총 (n/2)번 정렬을 해야 합니다. Quick sort가 평균 .. 2021. 8. 29.
[백준 1655번] 가운데를 말해요 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 제한 시간이 매우 짧은 (0.1초) 문제입니다. 반면 메모리는 상대적으로 넉넉한 편인 문제 같네요. 저는 다음과 같이 접근했습니다. 두 개의 Priority Queue minPQ, maxPQ를 둡니다. minPQ는 제일 작은 수가 top에, maxPQ는 제일 큰 수가 top에 위치합니다. 수를 입력 받아서 다음을 기준으로 push합니다. maxPQ의 element .. 2020. 12. 23.
[백준 2014번] 소수의 곱 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 언뜻 봐서는 어려워 보이는 수 관련 문제입니다. 문제 분류는 수학, 자료 구조, 정수론, 우선순위 큐라고 하네요. 얼핏 생각하면 다소 어려운 문제이긴 합니다. 숫자에 곱셈을 하는 정해진 횟수가 존재하지 않다 보니, 2, 2*2, 2*2*2, 2*2*2*....*2 등도 존재할 수 있기 때문에, 곱을 얼마나 해야 할지 감이 오질 않았어요. 고민 끝에 제가 .. 2020. 11. 21.

티스토리툴바