백준#1449 - 수리공 항승

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

1449번: 수리공 항승

그리디 알고리즘으로 분류된 1449 수리공 항승 입니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1449
{
    class Program
    {
        public class Pipe
        {
            int TapeLength;
            int PipeCount;
            List<int> PipeList = new List<int>();
            float Start;
            float End;
            public int Answer;
 
            //클래스값 입력받는 생성자.
            public Pipe(int length, int count, string[] pipe)
            {
                this.TapeLength = length;
                this.PipeCount = count;
                foreach(string p in pipe)
                {
                    this.PipeList.Add(int.Parse(p));
                }
                PipeList.Sort();
                Start = (float)PipeList[0] - 0.5f;
                Answer = 1;
                End = Start + TapeLength;
            }
 
            //수리가 필요한 파이프인지 검사. 이전 테이프가 덮었는지 검사.
            public bool NeedFix(int index)
            {
                return (float)PipeList[index] > End;
            }
 
            //파이프 한번 고치기.
            public void FixPipeOnce(int index)
            {
                if (NeedFix(index))
                {
                    Start = (float)PipeList[index] - 0.5f;
                    End = Start + TapeLength;
                    Answer++;
                }
            }
 
            //모든 파이프 고치기.
            public void FixAllPipe()
            {
                for (int i = 1; i < PipeList.Count; i++)
                {
                    FixPipeOnce(i);
                }
            }
        }
        static void Main(string[] args)
        {
            string[] numInput = Console.ReadLine().Split(' ');
            string[] pipeInput = Console.ReadLine().Split(' ');
            Pipe pipe = new Pipe(int.Parse(numInput[1]), int.Parse(numInput[0]), pipeInput);
            pipe.FixAllPipe();
            Console.WriteLine(pipe.Answer);
        }
    }
}
 

 

이 문제에서는 테이프를 어떻게 붙일지가 핵심이 되겠습니다.

 

ex) 수리가 필요한 파이프 : 7, 테이프 길이 : 3

고장난 파이프 : 1 3 5 7 11 15 19

 

이런식으로 있다고 생각하겠습니다.  우선 고장난 파이프를 오름차순 정렬하고 처음 1번 파이프에 테이프를 붙일텐데,

여러 방법이 있을겁니다. -1.0 ~ 2.0까지 붙이거나 0 ~ 3.0까지 붙이거나 등등

 

-1.0부터 2.0까지 붙인다면 1번 파이프는 수리가 되지만 나머지 고쳐야 할 파이프를 고려했을 때

2.0부터 모든 파이프를 고려해야 합니다.

 

0 ~ 3.0까지 붙일경우 3.0이후의 파이프를 고려하면 되지만 3.0의 경우 오른쪽으로 0.5를 더 고쳐야 합니다.

 

이와 같이 테이프를 고쳐야 하는 최대한 오른쪽으로 옮겨 붙여야 한다는 겁니다. 그래야 나머지 파이프 축에대해

고려해야할 범위가 줄어들게 됩니다.

 

1. 첫 파이프를 0.5 ~ 3.5까지 붙입니다. 이 변수를 Pipe클래스의 Start, End에 저장할 겁니다.

 

2. 3의 경우 아까의 End보다 작으므로 1을 수리하면서 함께 수리 되었습니다. (이를 NeedFix(int index)에서 확인함.)

 

3. 5는 End보다 크므로 다시 테이프를 붙여야 합니다. 가장 오른쪽으로 옮겨 4.5 ~ 7.5까지 붙여줍니다.

 

4. 이를 반복하는데 고장난 파이프 모두를 볼때 까지 해주면 되겠습니다.