코딍코딍
코딩기록
코딍코딍
전체 방문자
오늘
어제
  • 분류 전체보기 (271)
    • 개발 (2)
    • Java (1)
    • 스프링 (28)
    • JPA (11)
    • Git (3)
    • 알고리즘 (160)
      • 백준 (132)
      • 프로그래머스 (8)
      • SWEA (20)
    • 토이 프로젝트 (14)
      • 간단한 Springboot CRUD (1)
      • 게시판 프로젝트 (13)
    • 알고리즘 개념정리 (8)
    • 오류 해결 (13)
    • 보류 (0)
    • AWS (5)
    • 트러블 슈팅 (0)
    • 회고 (3)
    • CS (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

최근 글

티스토리

hELLO · Designed By 정상우.
코딍코딍

코딩기록

알고리즘/백준

1911번 : 흙길 보수하기

2023. 9. 26. 15:16

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

 

1911번: 흙길 보수하기

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000

www.acmicpc.net

 

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

 

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

 

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

 


소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    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 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) {
                return o1[0] - o2[0];
            }
        });

        int result = 0;
        int pre = -1; // 이전 널빤지 위치
        for (int i = 0; i < arr.length; i++) {
            // 이전 널빤지 위치가 현재 웅덩이를 침범하는 경우
            if(pre >= arr[i][0]) {
                // 이전 널빤지 위치가 현재 웅덩이를 덮는 경우
                if (pre >= arr[i][1] - 1) continue;
                int len = arr[i][1] - pre - 1; // 필요한 널빤지의 길이 (시작위치는 덮어져 있으니까 -1)
                if (len % l != 0) {
                    pre = pre + (len / l) * l + l;
                    result += len / l + 1;
                } else {
                    pre = arr[i][1];
                    result += len / l;
                }
            }
            else {
                int len = arr[i][1] - arr[i][0]; // 필요한 널빤지의 길이
                if (len % l != 0) {
                    pre = arr[i][0] + (len / l) * l + l - 1; // 시작 위치부터 덮으니까 -1
                    result += len / l + 1;
                } else {
                    pre = arr[i][1];
                    result += len / l;
                }
            }
        }

        System.out.println(result);
    }
}

 

해결방법

단순히 이전 널빤지의 위치를 보고 아래 두 가지 경우로 나누어 문제를 해결하였다.

1. 이전 널빤지 위치가 현재 웅덩이를 침범하는 경우

2. 이전 널빤지 위치가 현재 웅덩이를 침범하지 않는 경우

'알고리즘 > 백준' 카테고리의 다른 글

14562번 : 태권왕  (0) 2023.09.28
9489번 : 사촌  (0) 2023.09.27
5214번 : 환승  (0) 2023.09.26
4889번 : 안정적인 문자열  (0) 2023.09.25
20040번 : 사이클 게임  (0) 2023.09.22
    '알고리즘/백준' 카테고리의 다른 글
    • 14562번 : 태권왕
    • 9489번 : 사촌
    • 5214번 : 환승
    • 4889번 : 안정적인 문자열
    코딍코딍
    코딍코딍
    ㅎ2

    티스토리툴바