[BOJ / C++] 14465 : 소가 길을 건너간 이유 5

링크

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

14465번: 소가 길을 건너간 이유 5

 

풀이 과정 1 (실패)

처음 문제를 풀 때에는 벡터에 고장난 신호등의 리스트를 집어넣고, sort함수로 정렬해서 해당 신호등을 고쳤을 때 연속된 신호등의 개수가 K개 이상인지 확인하는 방식으로 문제를 풀었다. 하지만 그러다 보니 인덱싱의 문제도 있고, 무엇보다도 100%에서 계속해서 오답처리가 돼서 결국 방법을 바꿨다. 우선은 처음 했던 방식을 설명해 보겠다.

cont: 연속된 신호등의 개수

num: 고쳐야 하는 신호등의 개수

min: 현재 가장 적게 고쳐서 연속된 신호등 수가 K개가 될 수 있게 하는 신호등의 개수

각 변수는 위의 의미를 가지고 있고, 투 포인터 방식을 활용해서 left, right 두 변수를 두었다.

 

cont를 구하는 과정에서 if문을 여러 개 사용한 것은, cont를 구하는 방식이 left가 가리키는 신호등부터 right가 가리키는 신호등까지 고쳤다고 가정했을 때 그 사이에 정상 신호등이 몇개인지 세도록 만들다 보니 left과 right가 각각 맨 끝에 있을 경우 인덱싱에 문제가 발생해서 케이스를 나누었다.

아마 이 부분에서 뭔가 확인하지 못한 예외가 있기 때문에 100%에서 오답이 발생하는 것 같은데, 애시당초에 이렇게 if문을 여러 개 사용하는 것부터 뭔가 이상하다고 생각해서 다른 방법으로 문제를 다시 풀었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio; cin.tie(0); cout.tie(0);

    int N, K, B;
    cin >> N >> K >> B;

    vector<int> vec;
    int left = 0;
    int right = 0;

    for (int i = 0; i < B; i++) {
        int input;
        cin >> input;

        vec.push_back(input);
    }

    if (vec.size() == 1) {
        cout << "1";
        return 0;
    }

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

    int min = 10e10;
    while (right < vec.size()) {
        int num = right - left + 1;
        int cont = 0;

        if (right == 0) cont = vec[right + 1] - 1;
        else if (right == vec.size() - 1 && left != 0) cont = N - vec[left - 1];
        else if (right == vec.size() - 1 && left == 0) cont = N;
        else if (right != 0 && right != vec.size() - 1 && left == 0) cont = vec[right + 1] - 1;
        else cont = vec[right + 1] - vec[left - 1] - 1;

        if (cont >= K) {
            if (num < min) min = num;

            if (num == 1) {
                right++;
                //left++;
            }
            else left++;
        }
        else right++;
    }

    cout << min;

    return 0;
}

 

풀이 과정 2 (성공)

이 방식은 횡단보도의 개수 크기의 벡터를 우선 할당해주고, 0으로 초기화한 뒤 고장난 신호등이 있는 경우 1로 덮어씌우는 방식으로 문제 풀이를 시작한다.

신호등이 고장난 횡단보도를 모두 입력 받으면, 벡터의 처음부터(신호등이 1번부터이므로 인덱스 1부터) N번 인덱스까지 각 인덱스에 올때까지 고장난 신호등의 개수를 세서 저장한다.

이렇게 선행작업을 마치면, 다시 for문을 돌려서 i번째 횡단보도부터 연속된 K개의 신호등이 존재하도록 만들기 위해 고쳐야 할 신호등의 개수를 세면서 min 함수를 이용해서 그 중 최소값을 찾는다.

이 방식은 위에 방식대로 하다가 지쳐서 다른 블로그를 참고해서 다시 짜본 코드인데, 투 포인터보다는 완전탐색에 가까운 풀이 방식인 듯 하다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio; cin.tie(0); cout.tie(0);

    int N, K, B;
    cin >> N >> K >> B;

    vector<int> vec(N + 1);

    for (int i = 0; i < B; i++) {
        int input;
        cin >> input;

        vec[input] = 1;
    }

    for (int i = 1; i <= N; i++) {
        vec[i] += vec[i - 1];
    }

    int num = 10e10;
    for (int i = 1; i <= N - K + 1; i++) {
        num = min(num, vec[i + K - 1] - vec[i - 1]);
    }

    cout << num;

    return 0;
}