sort

Algorithm/Baekjoon Online Judge
[Java] 백준 1744 (수 묶기) Gold 4
Problem : https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net Approach Greedy한 문제이다. 아무 위치에 있는 두 수를 선택해도 되기 때문에, 먼저 정렬을 수행하는게 선택하기에 편하다. 문제 풀이에 앞서, 상식을 이용할 필요가 있다. 음수 두개를 곱하는 것이, 음수 두개를 더하는 것보다 값이 크다. 음수와 0은 곱하는 것이, 양수와 0은 더하는 것이 값이 크다. -1 두 개는 곱하는 것이, 1 두 개는 더하는 것이 값이 크다. ..
→2021.05.21
Algorithm/Baekjoon Online Judge
[Java] 백준 1202 (보석 도둑) Gold 2
Problem : 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 Approach 우선순위 큐를 활용한 Greedy 문제이다. 접근법을 떠올렸다면 쉽게 구현할 수 있다. (PriorityQueue 이용하여) 먼저 보석과 가방을 각각 무게 기준 오름차순으로 정렬한다. 각 가방에 대하여 가방의 무게보다 작은 보석들을 pq에 넣는다. (pq는 보석의 가치 기준 내림차순의 우선순위를 가진다...
→2021.04.17

• 이전
• 1
• 다음