문제 탐색하기
입력 자료 정리
- N은 그림의 개수 S는 정답으로 판단하기 위한 기준 높이다
- 이어서 들어오는 두 값은 각각 높이와 비용이다. N만큼 들어온다
해결방법 추론
- 처음에는 무게와 비용 입력값을 보고 배낭 문제로 생각했다
- 하지만 N은 30만인데, S가 2 X 10^7이고 C가 1000이기 때문에 해당 방법은 선택할 수 없었따
- 따라서 다른 방법을 선택해야했는데, 일단 이분탐색을 이용해서 시간복잡도를 줄이는 것이 우선이라고 생각했다
- 이분탐색의 대상으로 가장 적합한 것은 높이기 때문에 높이를 이분탐색의 대상으로 선정했다.
이분탐색을 하기위해서는 정렬되어있어야 하므로 배열을 높이로 오름차순 정렬했다 - 하지만 이 문제는 적합한 높이를 구하는 문제가 아니다. 적합한 높이를 구하면서 최대가 되는 비용도 구해야한다
- 높이로 정렬한 다음 최대 비용을 구하려면 정렬 조건을 추가해야하는데 그렇게 구현하기는 쉽지 않다
- 그렇다면 어떻게 해야할까? 다음과 같은 생각을 했다.
만약 현재 위치의 높이보다 낮은 높이 중에 앞에 세울 수 있는 높이가 있는데 그 값이 비용이 최대가 된다면 최대 비용을 구할 수 있지 않을까? - 위와같은 생각으로 구현하려면 dp방법을 선택해야한다.
- 정리하면 DP로 비용을 누적해나가면서 내 앞에 세울 수 있는 높이를 찾고 그 지점의 누적비용과 현재 지점의 비용을 더하면 될 것이다!
- 하지만 한가지 조금 더 생각하면 위 선택도 반례가 생길 수 있다.
만약 단순히 내 이전 높이의 누적 비용이 더 많다면 간단하게 반례가 생긴다 - 따라서 내 이전 높이의 누적 비용과도 비교해서 더 큰 값을 선택하도록 구현을 생각했다
- 또 한가지 더 반례가 생각났다. 만약 이분탐색 결과 찾지 못한다면 어떻게 할 것인가?
이 상황에서는 내 이전 높이와 현재 위치의 높이를 단순히 비교해서 더 큰 값으로 할 것이다 - 따라서 점화식은 다음과 같다
이분탐색 성공: dp[i] = Math.max(dp[i-1], dp[find] + arr[i][1]);
이분탐색 실패: dp[i] = Math.max(dp[i-1], arr[i][1]); - 위와같은 점화식을 통해 정답을 구할 수 있을 것이다!
시간복잡도 계산
- 시간복잡도는 dp를 진행하는 동안 n의 연산이 발생하고 이분탐색동안 log n의 연산이 발생하므로 O(n x logn)이 된다
- 따라서 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리
- n과 s는 int형 변수로 받고 높이와 비용은 int형 2차원 배열에 관리한다
배열은 nx2의 크기를 갖는다 - 또한 해당 배열은 0번 인덱스를 기준으로 정렬한다. 즉 높이를 기준으로 오름차순 정렬한다
- dp은 int형 1차원 배열로 선언한다. 값은 누적 비용이다
- dp[0]은 arr[0][1]로한다.
처음 설치하는 그림의 최적의 선택은 가장 낮은 높이를 설치하는 것이기 때문이다.
구현 코드 설계
- 1부터 n만큼 순회하면서 먼저 이분탐색을 진행한다
- 이분탐색은 높이 배열의 인덱스를 기준으로 진행한다.
범위 형태의 높이가 아닌 배열에 존재하는 높이만을 대상으로 해야하기 때문이다 - 이분탐색 결과 기준 위치와 탐색 위치의 높이차이를 구한다음 s이상인 경우 left를 조절하고 반대는 right를 조절한다
- 완성한 right를 리턴하면 이분탐색이 종료된다
- 찾은 경우는 0이상일 것이다. 조건에 맞게 다음 점화식을 구현한다
이분탐색 성공: dp[i] = Math.max(dp[i-1], dp[find] + arr[i][1]);
이분탐색 실패: dp[i] = Math.max(dp[i-1], arr[i][1]);
출력값 설계
- dp의 비용 누적 결과 n-1번째 인덱스의 값을 출력하면 정답이 된다
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[i][0] = h;
arr[i][1] = c;
}
Arrays.sort(arr,(o1, o2)->{
return o1[0] - o2[0];
});
int[] dp = new int[n];
dp[0] = arr[0][1];
for (int i = 1; i < n; i++) {
int find = binarysearch(i, arr, s);
if(find >= 0){
dp[i] = Math.max(dp[i-1], dp[find] + arr[i][1]);
}else{
dp[i] = Math.max(dp[i-1], arr[i][1]);
}
}
bw.write(dp[n-1]+"");
br.close();
bw.close();
}
private static int binarysearch(int pos, int[][] arr, int s) {
int left = 0;
int right = pos;
while(left <= right){
int mid = (left + right) / 2;
int diff = arr[pos][0] - arr[mid][0];
if(diff >= s){
left = mid + 1;
}else{
right = mid - 1;
}
}
return right;
}
}문제 링크
Software Developer