문제 링크
문제
티어: 골드 1
알고리즘: dp
N개의 도미노가 일렬로 놓여있다. 각 도미노는 위치 Xi에서 높이 Hi로 세워져 있다. 같은 위치에 2개 이상의 도미노가 놓여있는 경우는 없다. 홍준이는 도미노를 밀어서 왼쪽 또는 오른쪽으로 넘어뜨릴 수 있다. 도미노가 넘어지는 동안 만나게 되는 모든 도미노들은 같은 방향으로 넘어진다.
높이가 h이고 위치 x에 있는 도미노를 왼쪽으로 넘어뜨린 경우를 생각해보자. (x-h)와 x 사이에 위치한 모든 도미노들은 왼쪽 방향으로 넘어진다. 마찬가지로 오른쪽으로 넘어뜨렸다면, x와 (x+h) 사이에 위치한 모든 도미노들이 오른쪽 방향으로 넘어질 것이다.
이제 홍준이는 최소 개수의 도미노만 넘어뜨려서 모든 도미노들을 넘어뜨리려고 한다. 홍준이를 도와 최소 몇 개의 도미노를 넘어뜨리면 되는지 그 개수를 계산하는 프로그램을 작성하여라.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 300)
둘째 줄부터 N개의 줄에는 각 도미노의 위치와 높이를 나타내는 2개의 정수 Xi와 Hi가 주어진다. (1 ≤ Xi, Hi ≤ 2,000,000,000)
출력
첫째 줄에 모든 도미노를 넘어뜨리기 위해서 최소 몇 개의 도미노를 넘어뜨려야 하는지 출력한다.
풀이
모든 도미노를 넘어뜨리기 위해서 최소 몇 개의 도미노를 넘어뜨려야 하는지 출력해야 한다.
예제 입력 1로 풀이하면,
5
1 2
3 1
6 2
7 1
9 2- 처음 1 2를 넘어뜨리는 방법은 왼쪽으로 밀거나, 오른쪽으로 미는 경우다.
- 왼쪽으로 민다면 왼쪽 도미노는 없기 때문에 첫 번째 도미노까지만 넘어가고 총 한 번이 된다.
- 오른쪽으로 민다면 오른쪽 도미노는 있기 때문에 어디까지 넘어가는지 체크해야 한다.
두 번째까지 넘어가기 때문에 두 번째까지 총 한 번이 된다.
- 두 번재 3 1를 넘어뜨리는 방법 또한 왼, 오 미는 경우다.
- 왼쪽으로 민다면 왼쪽 도미노인 첫 번째 도미노까지 넘어가기 때문에 총 한 번이다.
- 오른쪽으로 민다면 최대 두 번째 도미노까지 넘어간다. (현재 도미노)
그런데 그 전에 첫 번째 도미노에서 오른쪽으로 민 경우도 두 번째 도미노까지 영향을 줘서 오른쪽으로 밀었기 때문에 그 값과 현재 도미노를 오른쪽으로 직접 밀었을 때와 + 첫 번째 도미노까지 최소 횟수를 비교해서 더 작은 값을 넣어줘야 한다.
더 작은 값은 1이기 때문에 최종적으로 오른쪽으로 민 경우는 1이 된다.
..
5. 다섯 번째 9 2를 넘어뜨리는 방법은 왼, 오 미는 경우다.
- 왼쪽으로 미는 경우 최대 세 번째인 6 2 도미노를 넘어뜨린다.
그리고 나머지 1, 2 번째 도미노도 넘어뜨려야 하는데 이 값은 이미 구했다.
그래서
2번 째까지 넘어뜨리는 최솟값 + 1,
3번 째까지 넘어뜨리는 최솟값 + 1,
4번 째까지 넘어뜨리는 최솟값 + 1
5번 째까지 넘어뜨리는 최솟값 (앞에서 이미 업데이트되었을 수 있음)을 비교해야 되고,
여기서 2번 째까지 넘어뜨리는 최솟값 + 1이 2로 가장 작기 때문에 답은 2가 된다.
5번에서 왼쪽으로 미는 경우 세 번째까지 넘어뜨렸는데, 2번 째까지만 고려하는 것이 아닌 3, 4까지 고려해줘야 한다. 왜냐하면 정확히 1 ~ 3까지나 1 ~ 4까지 넘어뜨리는 최소 횟수가 1 ~ 2까지 최소 횟수보다 작을 수 있기 때문이다.
이를 토대로 dp를 정의하면 dp[A]가 되고,
dp[A]는 1 ~ A까지 도미노를 넘어뜨리는 최솟값을 저장한다.
ex) dp[3]은 1 ~ 3까지 도미노를 넘어뜨리는 최솟값
핵심은 각 도미노에서 직접 미는 경우를 구하는 것이고, 밀었을 때 상태를 메모제이션한 값을 통해구하는 것이다. (물론 직접 밀지 않았을 때와 비교해 그 값이 더 작다면 결국 직접 밀지 않은 값이 들어오긴 한다. 그렇지만 넘어간건 똑같다.)
소스 코드
import java.io.*;
import java.util.*;
class Dominoes implements Comparable<Dominoes> {
long x, h;
public Dominoes(long x, long h) {
this.x = x;
this.h = h;
}
@Override
public int compareTo(Dominoes other) {
return Long.compare(this.x, other.x);
}
}
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Dominoes[] dominoes = new Dominoes[N + 1];
for(int i=1; i<=N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
dominoes[i] = new Dominoes(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
}
Arrays.sort(dominoes, 1, N + 1);
int[] dp = new int[N + 1];
for(int i=1; i<=N; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;
for(int i=1; i<=N; i++) {
//오른쪽으로
int maxNum = passedMaxDominones(true, i, dominoes);
dp[maxNum] = Math.min(dp[maxNum], dp[i - 1] + 1);
//왼쪽으로
int minNum = passedMaxDominones(false, i, dominoes);
if(minNum == 1) {
//다 넘어갔다면
dp[i] = 1;
} else {
//다 넘어가지 않았다면
for(int j=minNum - 1; j<=i - 1; j++) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
System.out.println(dp[N]);
}
static int passedMaxDominones(boolean right, int std, Dominoes[] dominoes) {
int result = std;
if(right) {
long max = dominoes[std].x + dominoes[std].h;
for(int i=std + 1; i<=N; i++) {
if(max < dominoes[i].x) {
break;
}
result = i;
max = Math.max(max, dominoes[i].x + dominoes[i].h);
}
} else {
long min = dominoes[std].x - dominoes[std].h;
for(int i=std - 1; i>=1; i--) {
if(dominoes[i].x < min) {
break;
}
result = i;
min = Math.min(min, dominoes[i].x - dominoes[i].h);
}
}
return result;
}
}