[백준 BOJ] 1449번 수리공 항승 (C++/cpp)

문제 설명

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

 

(오류가 있는지 플래카드가 안 뜬다ㅠㅜ)

 

접근 방법 - 정렬을 활용한 그리디 알고리즘 문제

백준의 1449번 문제는 정렬을 활용하여 문제 해결에 접근해야 하는 그리디 알고리즘 문제이다.

해당 문제는, 물이 새는 공간에 대해 테이프를 붙이고자 하는데 최소 몇 개의 테이프가 필요한지를 구하여 출력해야 하는 문제이다.

이때 테이프의 길이가 가능한 선에서라면 여러 개의 구멍을 막을 수 있기 때문에, 테이프를 부착할 때 어디까지 막을 수 있는지를 관건으로 삼아야 할 듯하다.

필자는, 구멍이 난 공간의 위치들을 오름차순 정렬을 한 뒤에, 하나씩 테이프를 붙여보며 여러 개를 막을 수 있는지를 확인하게끔 하였다.

이때 구멍 위치가 순서대로 나열되어 있다는 보장이 없기 때문에 정렬을 반드시 해주고 연산을 취해야 한다.

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 구멍의 개수(n)와 테이프 하나의 길이(l)를 입력받는다.

 

2) 구멍 위치를 저장할 벡터 v를 미리 선언해 둔다.

그리고 이 이후로의 입력값들을 v에 하나씩 저장해 둔다.

 

3) 구멍 위치들을 저장한 벡터 v에 대하여, sort() 함수를 사용하여 오름차순 정렬을 수행한다.

 

4) 사용할 테이프의 개수를 저장할 변수 count를 선언해 둔다.

이때 필자는 테이프를 하나 사용할 때마다 count의 값을 1씩 늘리게끔 하려 하니, 0으로 미리 초기화해 두었다.

 

5) 반복문을 활용하여, 아래의 연산을 취하게끔 하였다.

- 벡터 v가 구멍의 위치들을 저장해 둔 곳이기 때문에, i의 값과 무관하게 어쨌든 테이프를 하나 사용하긴 해야 한다.

그렇기 때문에, 우선은 count의 값을 1 증가시켜 테이프를 하나 사용한 것으로 가정한다.

- tape 변수를 활용하여, 앞서 사용한 테이프의 끝점을 해당 변수에 저장하게끔 하였다.

테이프의 시작점(현재 v[i]값)에 테이프 길이(l)를 더하였고, 여기에 1을 뺀 값으로 변수를 설정하였다.

이때 1을 빼는 이유는, 구멍 난 공간에 테이프를 붙일 때 좌우 양옆으로 0.5씩 간격을 두고 붙여야 한다는 점이 문제에 명시되어 있기 때문이다.

(예를 들어, 1, 2번 공간을 길이가 2인 테이프로 막는다고 가정할 때, 0.5 ~ 2.5에 테이프가 부착되도록 해야 한다.)

- 새로운 반복문을 만들어서, 앞서 부착한 테이프가 다른 구멍도 막을 수 있는지를 탐색해 보도록 한다.

탐색하는 v[i]값이 테이프의 끝점인 tape값 이전에 위치한다면, 이는 앞서 사용한 테이프로 막을 수 있는 구멍임을 의미한다. i를 증가시켜 다음 구멍도 해당사항이 있는지 확인한다.

만약 tape값을 넘어서게 된다면, 반복문을 종료한 뒤 다른 테이프를 통해 막을 수 있도록 한다.

 

6) 5)의 연산이 모두 종료되었다면, 최종적으로 저장된 count의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 1449번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n, l;
    cin >> n >> l;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        v.push_back(num);
    }
    sort(v.begin(), v.end());

    int count = 0;
    for (int i = 0; i < v.size(); ) {
        count++;
        int tape = v[i] + l - 1;
        while (i < v.size() && v[i] <= tape) {
            i++;
        }
    }
    cout << count << endl;
}

 

제출 결과

(2024.01.01 백준 1449번 문제 제출 결과)