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

 

문제에서 말하고 있는 내용은 단순하다.

'물이 새는 위치 N개를 길이가 L인 테이프 몇 개를 이용해서 구멍을 막을 수 있는가'이다.

하지만 고려해야할 부분이 존재한다.

테이프의 길이가 L이고, 어떤 지점 x에 붙이면 x - 0.5부터 x + L - 0.5까지를 막을 수 있다라는 것이다.

예를 들어서,

 

• 물이 새는 위치가 1일 때, 테이프는 0.5 ~ 2.5까지를 막는다.
• 그 다음 구멍이 3에 있다면, 기존 테이프로는 못 막기 때문에 새로운 테이프가 필요하다.

그렇기 때문에 기준점과 테이프로 가려지는 범위를 정확하게 구하는 것이 중요하다.

 

 

 

그 점을 고려하여 문제를 풀어보자.

 

물이 새는 위치와 테이프의 길이, 그리고 필요한 테이프의 개수를 선언해주자.

그리고 물이 새는 위치는 벡터에 저장하여 정렬과 순차접근이 가능하도록 하자.

int n, l;
int cnt = 0;

cin >> n >> l;

vector<int> v;
for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    v.push_back(a);
}

 

그리고 우리는 입력받은 벡터를 정렬해주어야 한다.

왜 정렬하나요?

→ 가장 앞의 위치부터 순차적으로 테이프를 붙여서 구멍을 막아야하기 때문.

정렬이 된 상태로 입력을 받으면 좋겠지만, 그렇지 않으니 정렬을 해주어야 한다.

sort(v.begin(), v.end());

 

첫 번째 물이 새는 위치를 기준으로 테이프를 하나 붙이자.

int tape = v[0] - 0.5 + l;
cnt++;

 

왜 v[0] - 0.5 을 하나요?

→ 구멍 기준 왼쪽 0.5부터 시작해야 하기 때문.

 

+ l 은 테이프의 길이만큼 덮어야하기 때문에 l 을 더해주는 것이다.

처음 시작할 때는 무조건 테이프 한 개가 필요하기 때문에 cnt 의 값을 1만큼 증가시켜 준다.

 

구멍을 하나 막았으니, 나머지 구멍도 막아주어야 한다.

for(int i = 0; i < n; i++){
    if(tape < v[i] + 0.5){
        tape = v[i] - 0.5 + l;
        cnt++;
    }
}

 

v[i] + 0.5 는 구멍의 오른쪽 경계이고,

tape는 현재 테이프가 덮을 수 있는 마지막 위치이다.

 

테이프의 길이가 구멍을 커버하지 못한다면,

테이프를 하나 더 사용해야하기 때문에 l 을 더하고, cnt 의 값도 하나 증가시켜준다.

 

728x90

 

이렇게 하면 문제 풀이 끝이다.

제출해보자.

틀렸다.

틀린 이유가 뭘까..?

 

다시 코드를 보자.

-0.5를 하는데 int 타입?

이러니까 틀렸다.

 

int 타입이 아닌 double 로 바꾸고, 강제 형변환도 진행하자.

double tape = (int)(v[0] - 0.5 + l);

 

이렇게 수정을 하고 제출하면~~

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

//수리공 항승
using namespace std;

int n,l;
int cnt = 0;

int main(){
    cin >> n >> l;

    vector<int> v;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());
    double tape = (int)(v[0] - 0.5 + l);
    cnt++;

    for(int i = 0; i < n; i++){
        if(tape < (int)(v[i] + 0.5)){
            tape = (int)(v[i] - 0.5 + l);
            cnt++;
        }
    }
    cout << cnt << '\n';
    return 0;
}

 

 

실버3 난이도의 문제였다.

문제의 접근 자체는 어렵지 않았는데 고려해야할 부분이 두 가지 존재했다.

첫째는 좌우로 0.5씩 여유공간. 

두번째는 변수의 타입 지정.

두 가지만 잘 캐치했다면 한번에 맞았을 수도 있었는데 조금은 아쉬움이 남는 문제 풀이였던 것 같다.

다음엔 잘 하자..^^;;

 

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요.

피드백 환영입니다☺️