반응형
https://www.acmicpc.net/problem/2170
문제
매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.
이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.
풀이
문제를 해결하기 위해 라인 스위핑이라는 알고리즘이 무엇인지 찾아보았고 한 쪽 방향에서부터 시작해서 다른쪽 방향으로 스캔해가면서 푸는 방식
을 라인 스위핑이라고 합니다.
이게 무슨뜻인지 많이 고민했고 선을 종이에 그려보면서 어떤 경우의 수가 나올까 고민해보았습니다.
- 많은 경우의 수가있지만 조금이라도 줄이기 위해 선의 시작 점을 기준으로 정렬해서 앞이 긴 경우를 제외하고 시작했습니다.
- 이전 선의 종료 지점보다 현재 선의 시작 지점이 작고(겹친다!), 이전 선의 종료지점보다 현재 선의 종료지점이 작다.
- 즉, 현재 선이 이전의 선에 포함된다. 이 경우에는 현재 선을 버려도 되는 선이다. (겹쳐지기 때문)
- 이전 선의 종료 지점보다 현재 선의 시작 지점이 작고 (겹친다.), 이전 선의 종료지점보다 현재 선의 종료지점이 길다.
- 즉, 현재 선이 이전선과 겹쳐져 있지만 종료지점이 더 길기 때문에 길이를 추가해주어야 한다.
- 이때, 추가해야 하는 길이는 (현재 선의 종료지점 - 이전 선의 종료지점)이 된다.
- 이전 선의 종료 지점보다 현재 선의 시작 지점이 크다. (겹치지 않음)
- 겹치지 않는 선이기 때문에 새롭게 추가해주면 된다.
코드를 보자.
값 입력 및 정렬
경우의 수를 줄이기 위해서 입력된 값을 정렬해주었다.
ArrayList<Line> lines = new ArrayList<>();
StringTokenizer st;
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
lines.add(new Line(x, y));
}
Collections.sort(lines, (x, y) -> x.x - y.x);
public static class Line{
int x;
int y;
public Line(int x, int y){
this.x=x;
this.y=y;
}
}
라인 스위핑
첫 번째 시작점을 가진 선부터 끝까지 스캔하면서 길이를 체크한다.
Line before = lines.get(0);
int sum = before.y - before.x;
for(int i=1; i<lines.size(); i++){
Line now = lines.get(i);
if(now.x <= before.y && now.y <= before.y) continue;
if(now.x <= before.y){
sum += now.y - before.y;
}else{
sum += now.y - now.x;
}
before = now;
}
System.out.println(sum);
전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Line> lines = new ArrayList<>();
StringTokenizer st;
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
lines.add(new Line(x, y));
}
Collections.sort(lines, (x, y) -> x.x - y.x);
Line before = lines.get(0);
int sum = before.y - before.x;
for(int i=1; i<lines.size(); i++){
Line now = lines.get(i);
if(now.x <= before.y && now.y <= before.y) continue;
if(now.x <= before.y){
sum += now.y - before.y;
}else{
sum += now.y - now.x;
}
before = now;
}
System.out.println(sum);
}
public static class Line{
int x;
int y;
public Line(int x, int y){
this.x=x;
this.y=y;
}
}
}
결과
반응형
'백준' 카테고리의 다른 글
[JAVA] 백준 1515, 수 이어쓰기 (0) | 2024.12.21 |
---|---|
[JAVA] 백준 15889 라인 스위핑 (1) | 2024.05.11 |
[JAVA] 백준 15787 (0) | 2024.04.17 |
[JAVA] 백준 2961 (0) | 2024.04.17 |
[JAVA] 백준 11723 (0) | 2024.04.17 |