[C++] 백준 1449번: 수리공 항승

🔗 문제

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

 

🖍 풀이

 

✔️ 최적의 해 구하는 법
테이프의 개수를 최소로 쓰기 위해 한 테이프로 여러 구멍을 막아야 한다.

 

[i번째 구멍 ~ 최대 j 구멍까지 거리] + [여유 거리 (1)]이 테이프 길이를 초과한다면?

그 바로 직전까지 i ~ j-1 는 한 테이프로 막을 수 있다. 

 

 

먼저 입력이 오름차순이 아닐 수 있기에 구멍난 위치들을 정렬한다.

#include <algorithm>

...

std::sort(pipe, pipe+N);

 

그 후에 생각했던 가설을 코드로 옮겼다.

for(int i=0; i<N; ++i) // 테이프의 시작점
    {
        for(int j=i+1; j<N;j++) // 테이프의 끝점
        {
            if(pipe[j]-pipe[i] + 1 > L) // i ~ j 거리 + 여유 거리 < 테이프 길이
            {
                i=j;
                j=i;
                ++tape;
            }
        }
    }

 

이렇게 코드를 짜면 마지막 테이프는 카운팅 되지 않아 출력할 때 1을 더해준다.

std::cout << tape + 1;

 

다듬은 후

    std::sort(pipe, pipe+N);
    int start = pipe[0];
    for(int i=1; i<N; ++i)
    {
        if(pipe[i] - start >= L)
        {
            start = pipe[i];
            ++tape;
        }
    }

• 이중 포문를 단일 포문으로 변경
  • 테이프를 붙일 때 마다 새로운 테이프 시작점을 start에 저장
  • pipe[0]은 이미 시작점이기 때문에 기존 j문 시작을 1부터 시작
• if(start -pipe[i] +1 > L)을 if(start-pipe[i] >= L)문으로 변경

 

 

💾  소스

#include <iostream>
#include <algorithm>
#define MAX 10001

int main()
{
    int N, L;
    int tape = 0;
    int pipe[MAX];
    
    //input
    std::cin >> N >> L;
    for(int i=0; i<N; ++i)
        std::cin >> pipe[i];
    
    //solve
    std::sort(pipe, pipe+N);
    int start = pipe[0];
    for(int i=1; i<N; ++i)
    {
        if(pipe[i] - start >= L)
        {
            start = pipe[i];
            ++tape;
        }
    }
    
    //output
    std::cout << tape +1;
    return 0;
}