[백준] 19584 난개발

1. 문제

www.acmicpc.net/problem/19584

19584번: 난개발

2. 접근방법

수평으로 철길을 만들어서 가장 많은 통행량을 부수는 문제

 

좌표 압축을 하고 누적합을 하면 풀 수 있는 문제

 

수평으로 놓는 것이다 보니 x값은 필요 없다.

 

좌표압축은 모든 y값 좌표를 중복제거, 정렬을 한 뒤

각 값에 index를 매겨서

쿼리로 매칭된 값이 입력으로 들어오면 그 index에만 쿼리를 적용하는 방법으로 구현하면 된다.

 

중복제거, 정렬을 하는데는 TreeSet을 사용하였고

 

각 값에 index를 해쉬맵으로 매칭시켰다.

 

이제 각 쿼리에 맞게 값을 증가시켜주고

 

가장 합이 큰 값을 구해서 출력하면 된다.

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class G3_19584난개발 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int numtoy[] = new int[N];
		TreeSet<Integer> mini = new TreeSet<Integer>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			numtoy[i] = Integer.parseInt(st.nextToken());
			mini.add(numtoy[i]);
		}
		
		ArrayList<Integer> miniset = new ArrayList<Integer>(mini);
		HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
		for(int i = 0 ; i < miniset.size() ; i++)
			hashmap.put(miniset.get(i), i);
		
		long sum[] = new long[miniset.size()+1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken())-1;
			int v = Integer.parseInt(st.nextToken())-1;
			long c = Long.parseLong(st.nextToken());
			int y1 = numtoy[u];
			int y2 = numtoy[v];
			y1 = hashmap.get(y1);
			y2 = hashmap.get(y2);
			if (y1 > y2)
				y1 = y2 ^ y1 ^ (y2 = y1);
			sum[y1] += c;
			sum[y2+1] -= c;
		}
		long max = sum[0];
		for(int i = 1 ; i < sum.length ; i++) {
			sum[i] += sum[i-1];
			max = Math.max(sum[i], max);
		}
		System.out.println(max);
	}

}

4. 마치며

예전에 도전했다가 좌표압축을 몰라서 삽질 엄청하다 포기 했었는데

최근에 다른 문제 풀면서 좌표 압축을 알게 되어 다시 도전해서 성공했슴니다.