[백준] 1449 - 수리공 항승

1. 문제

1449번: 수리공 항승

2. 개요

왼쪽에서 정수만큼 떨어진 위치에 물이 새고 있는 파이프가 있다.

수리공은 L 길이의 테이프를 무한개 가지고 있다.

테이프로 파이프를 막을 때는 구멍이 있는 곳 좌, 우 0.5cm만큼 간격을 줘야 물이 새지 않는다.

테이프를 자를 수 없고, 겹쳐 붙일 수 있을 때, 필요한 테이프의 최소 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

물이 새는 곳의 정보를 받아 오름차순 정렬해둔다.

물이 새는 곳은 무조건 1곳 이상이므로 테이프를 1개 이상 쓰게되므로 답을 1로 초기화해둔다.

첫 위치 - 0.5가 첫 테이프의 왼쪽 끝이 된다.

물이 새는 위치를 순서대로 탐색하면서 해당 위치 + 0.5의 값 - 테이프의 왼쪽 끝 위치가 테이프의 길이 이하라면, 다음 위치로 넘어간다.

만약 테이프의 길이를 초과한다면 전 위치에서 테이프를 끊고 현재 위치에서 새로 테이프를 붙여야 하므로 테이프의 왼쪽 위치를 현재 위치 - 0.5로 갱신하고 답을 1만큼 늘려준다.

물이 새는 모든 위치에 대해 위 작업을 반복하고 탐색을 마쳤다면 답을 출력한다.

3-2. Python

import sys

N, L = map(int, sys.stdin.readline().split())

answer = 1

leaks = list(map(int, sys.stdin.readline().split()))
leaks.sort()

l, r = leaks[0], leaks[0]

for leak in leaks:
    if leak + 0.5 - l <= L:
        r = leak + 0.5

    else:
        answer += 1
        l, r = leak - 0.5, leak - 0.5

print(answer)

3-3. C#

namespace boj_1449
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int L = int.Parse(input[1]);

            int answer = 1;

            int[] leaks = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            Array.Sort(leaks);

            float l = leaks[0] - 0.5f;
            float r = leaks[0] - 0.5f;

            foreach (int leak in leaks)
            {
                if (leak + 0.5f - l <= L)
                    r = leak + 0.5f;

                else
                {
                    answer++;
                    l = leak - 0.5f;
                    r = leak - 0.5f;
                }
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}