티스토리 뷰

PS/boj

boj)1911 - 흙길 보수하기

kingsubin 2020. 8. 31. 16:42
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 웅덩이 갯수
        int L = Integer.parseInt(st.nextToken()); // 널빤지 길이

        int[][] arr = new int[N][2]; // 물웅덩이의 시작, 끝 위치
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); // 시작 위치
            arr[i][1] = Integer.parseInt(st.nextToken()); // 끝 위치
        }

        // 물 웅덩이 정렬
        // 시작위치가 같으면 끝자리 오름차순
        // 시작 위치를 기준으로 오름차순
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return Integer.compare(o1[1], o2[1]);
                }
                return Integer.compare(o1[0], o2[0]);
            }
        });

        int ans = 0; // 널빤지 갯수
        int range = 0; // 널빤지를 웅덩이에 덮엇을때, 덮을 수 있는 범위

        for (int i = 0; i < N; i++) {
            if (arr[i][0] > range) { // 시작위치가 범위보다 클 경우
                range = arr[i][0];
            }
            if (arr[i][1] >= range) { // 끝위치가 범위보다 클 경우
                while (arr[i][1] > range) {
                    range += L;
                    ans++;
                }
            }
        }

        System.out.println(ans);
    }
}

 

- 어떻게 풀지 생각도 안나서 다른 풀이 봄

- 혼자 다시 풀어라고하면 다시 풀 수 있을지 모르겠음.... 

 

 

- 널빤지를 시작 위치부터 끝까지 덮어야함. 전부 다르게 보지않고 시작 위치를 기준으로 오름차순 정렬하면

차근차근 접근할 수 있음.

 


https://www.acmicpc.net/problem/1911

'PS > boj' 카테고리의 다른 글

boj)12018 - Yonsei TOTO  (0) 2020.08.31
boj)2012 - 등수 매기기  (0) 2020.08.31
boj)8958  (0) 2020.08.29
boj)4344  (0) 2020.08.29
boj)10996  (0) 2020.08.29