[백준 / BOJ] 1253 좋다
문제 출처 : www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N개의 수열이 주어진다. 이때, N개의 수 중에서, 어떤 수가 다른 수 두개의 합으로 나타내진다면, 그 수를 좋다 라고한다. 좋은수가 몇개인지 구하는 문제다. (위치가 다르면 값이 같아도 다른 수 이다.) 풀이 완전탐색으로 풀경우 O(N^3)이 되어서 시간초과가 난다. 시간초과를 피하기 위해, 이분탐색으로 풀은 문제다. 로직은 간단한데, 수열 N에서 i번째수를 Ni라 할때, 1. 좋은 수 인지 판단할 수 Ni를 하나 지정한다..
[백준 / BOJ] 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 상덕이는 보석을 털기로 결심했다. 보석점에 총 N개의 보석이 있고, 각 보석은 M의 무게, V의 가격을 갖고있다. 상덕이는 K개의 가방을 갖고있고, 각 가방에는 최대 Ci무게의 보석을 담을수있다. 이때, 각 가방에는 최대 한개의 보석만 담을수있다. 상덕이가 홈칠수있는 보석의 최대 가격을 출력하는 문제다. 풀이 보석의 수 N..