[1911번] 흙길 보수하기

문제 기출 : [https://www.acmicpc.net/problem/1911]

 

 

풀이 방법

[그리디알고리즘] 접근   생각하는 것을 코딩하는 것은 정말 쉬운일이 아닌 것 같다..하핳 1. index 값에 편하고 빠르게 접근하기 위해 객체 정렬을 진행한다. 2. 덮을 수 있는 널빤지의 index 기반 범위를 구하고 해당 범위에 널빤지길이를 더해 나아가면서 널빤지를 카운팅하기만 하면 된다.

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			StringTokenizer tokens = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(tokens.nextToken());
			int L = Integer.parseInt(tokens.nextToken());
			int[][] poolInfo = new int[N][2];
			int plankCount = 0;
			int range = 0;

			for (int i = 0; i < N; i++) {
				tokens = new StringTokenizer(br.readLine(), " ");
				poolInfo[i][0] = Integer.parseInt(tokens.nextToken());
				poolInfo[i][1] = Integer.parseInt(tokens.nextToken());
			}

			Arrays.sort(poolInfo, new Comparator<int[]>() {
				@Override
				public int compare(int[] arg0, int[] arg1) {
					if (arg0[1] == arg1[1]) {
						return arg0[0] - arg1[0];
					} else {
						return arg0[1] - arg1[1];
					}
				}
			});

			for (int i = 0; i < N; i++) {
				if (poolInfo[i][0] > range) {
					range = poolInfo[i][0];
				}
				
				if (poolInfo[i][1] >= range) {
					while (poolInfo[i][1] > range) {
						range += L;
						System.out.println(range);
						plankCount++;
					}
				}
			}

			System.out.println(plankCount);

		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}