백준 BaekJoon 17262번: 팬덤이 넘쳐흘러 [Java]

2021-01-21

---

문제

선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬들을 위해 가끔씩 학교에 가 줘야 한다. 욱제는 백숙이 끓는 걸 지켜봐야 해서 가게를 오래 비울 수 없다. 그래서 욱제는 한 번 학교에 간 뒤 최소 시간동안 머물다가 모든 팬들과 한 번씩 인사를 하고 학교를 떠나려고 한다.

욱제는 임의의 시각에 학교에 오거나 학교를 떠날 수 있고, 단 한 번의 왕복만 한다. 동시에 여러 팬들에게 인사를 끝낼 수도 있다. 욱제는 잘생겨서 인사하면 팬들이 심쿵사로 바로 쓰러지기 때문에 인사를 하는데 소요되는 시간은 0이라고 하자.

예를 들어 3명의 팬 A, B, C가 학교에 머무르는 시간이 <그림 1>과 같다고 하자. 이 경우 시각 2에 3명의 팬이 모두 학교에 있으므로, 욱제는 시각 2에 학교에 와서 3명에게 동시에 인사를 하고 바로 가게로 돌아갈 수 있다. 시각 3이나 4도 마찬가지이다. 이때 욱제가 학교에 머무는 시간의 총합은 0이다.

다른 예로 2명의 팬 A와 B가 학교에 있는 시간이 <그림 2>와 같다고 하자. 욱제는 시각 4부터 시각 5까지 학교에 머물면서 시각 4에 A와, 시각 5에 B와 인사를 하고 학교를 떠날 수 있다. 이때 욱제가 학교에 머무는 시간은 1이다.

백숙집 주방 이모 효빈이는 N명의 팬들이 학교에 머무르는 시간 [s, e]들을 몰래 조사했다. 효빈이는 욱제가 학교에 머무르는 시간을 계산해서 그 시간동안 땡땡이를 치기로 했다. 효빈이와 함께 욱제가 학교에 머무르는 최소의 시간을 계산해 보자!

입력

첫째 줄에 욱제의 열렬한 팬의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에 걸쳐, 각 줄에 정수 si, ei (1 ≤ si ≤ ei ≤ 100,000)가 순서대로 주어진다. 이는 i번째 팬이 학교에 있는 시간 [si, ei]을 의미한다.

출력

욱제가 학교에 머물러야 하는 최소의 시간을 출력한다.

---

import java.util.Scanner;

public class TemplateA {
	public static void main(String[] args){
		Scanner scan = new Scanner (System.in);	
		
		int fan = scan.nextInt();
		int [][] arr = new int [fan][2];
		
		
		for(int i =0; i < fan; i++) {
			for(int j = 0; j < 2; j++) {
				arr[i][j] = scan.nextInt();
			}
		}
		
		int start = arr[0][0];
		//초기 시작값은 처음 학생의 머무는 시간으로 준다.
		int end = arr[0][1];
		//초기 끝값은 처음 학생의 머무는 시간으로 준다.
		//(사실 어떤학생을 주던 크게 상관은 없는데, 순서 때문에 구현하기 까다로워짐)
		
		int count = 0;
		//머무는 시간을 셀 변수
		for(int i = 1; i < fan; i++) {
			//첫학생은 이미 초기값 셋팅으로 들어가 있음으로
			// 2번째 학생부터 비교하면됨
			for(int j = 0; j < 1; j++) {
				if(arr[i][j + 1] < start) {
					count += start - arr[i][j + 1];
					start = arr[i][j];
					//학생의 머무는 시간의 끝값이 다른 학생의 스타트 값보다
					//작으면, 겹치는 시간이 없음
					//머무는 시간에 둘의 차를 더해주고
					//시작값은 더 먼저 도착하는 학생의 값으로 변경한다.
				}else {
					if(arr[i][j] > end) {
						count += arr[i][j] - end;
						end = arr[i][j + 1];
					}
					// end 값에 저장된 학생의 값보다 다른 학생의 시작하는 값이 크면,
					//마찬가지로 겹치는 시간이 없음 때문에 끝값은 그 다른 학생이 떠나는 시간으로 초기화하고
					// 카운트에 해당하는 값들의 차이를 넣어줌
				}
			}
		}
		
		System.out.println(count);
	}
}
	

 

출처링크 : www.acmicpc.net/problem/17262

17262번: 팬덤이 넘쳐흘러