[BOJ] 1911번 흙길 보수하기

문제

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

입력

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

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

출력

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

코드

• C++ 17

#include <iostream> #include <cmath> #include <algorithm>   using namespace std;   int N, L, Ans; pair<int, int> Puddles[10000];   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       cin >> N >> L;     for (int i = 0; i < N; ++i)         cin >> Puddles[i].first >> Puddles[i].second;       sort(Puddles, Puddles + N);          int s = 0;     for (int i = 0; i < N; ++i)     {         // 시작지점은 이전에 놓은 막대와 겹치지 않은 웅덩이의 부분이다.         s = max(Puddles[i].first, s);           // 웅덩이를 메우기 위해 얼만큼의 길이가 필요한지 구한다.         int diff = Puddles[i].second - s;           // 웅덩이를 완전히 메우려면 Ceil(diff / L)이어야 한다.         int count = (diff + L - 1) / L;           // 정보를 업데이트한다.         Ans += count;         s += count * L;     }       cout << Ans; }

• C# 6.0

using System;   namespace ForAlgoCsharp {     class Program     {         static int N, L, Ans;         static Tuple<int, int>[] Puddles;           static void Main(string[] args)         {             string[] inputs = Console.ReadLine().Split();             N = Convert.ToInt32(inputs[0]);             L = Convert.ToInt32(inputs[1]);             Puddles = new Tuple<int, int>[N];               for (int i = 0; i < N; ++i)             {                 int st, e;                 inputs = Console.ReadLine().Split();                 st = Convert.ToInt32(inputs[0]);                 e = Convert.ToInt32(inputs[1]);                   Puddles[i] = new Tuple<int, int>(st, e);             }               Array.Sort(Puddles);               int s = 0;             for (int i = 0; i < N; ++i)             {                 s = Math.Max(Puddles[i].Item1, s);                 int diff = Puddles[i].Item2 - s;                 int count = (diff + L - 1) / L;                 Ans += count;                 s += count * L;             }               Console.Write(Ans);         }     } }

• Python 3

from sys import stdin input = stdin.readline   N, L = map(int, input().split()) p = [ [ int(x) for x in input().split() ] for i in range(N) ]   p.sort()   res, s = 0, 0 for i in range(N):     s = max(p[i][0], s)     diff = p[i][1] - s     count = (diff + L - 1) // L     res += count     s += count * L   print(res)

복기

Python3에서 내장 input()과 sys.stdin.readline()의 성능이 무려 400ms 차이가 났다.