[백준/C++] 14465번 소가 길을 건너간 이유 5

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

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

내가 푼 코드

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

using namespace std;

int n, k, b;
int cnt,num;
bool arr[100001];
bool cmp[100001];

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

    cin >> n >> k >> b;

    for (int i = 0; i < b; i++) {
        cin >> num;
        //arr[i] = num;
        arr[num] = true; 
    }    
    int ans = 987654321;
    int p1=1 ,p2 = 1;
    int tmp = p2;
    
    while (1) {
        if (cmp[p1] != arr[p2]) {
            cnt++;          
        }
        p1++;
        p2++;        
        if (p1 > k) {            
            ans = min(ans, cnt);
            cnt = 0;
            tmp++;
            p1 = 1;
            p2 = tmp;
            if (p2 + k-1 > n) break;
        }
    }       
    cout << ans;
    return 0;
}

 

문제풀이

투포인터와 슬라이딩 윈도우 문제이다.

N개의 신호등을 가지고 있는 배열 arr과 K개의 연속된, 잘 작동하는 신호등 배열cmp를 통째로 비교해주었다.

참조 :  https://yongmemo.tistory.com/16

 

위 사진을 보면 이해가 쉬울 것이다.

위 코드를 O(N)의 시간복잡도로 개선한 코드는 다음과 같다.

#include<iostream>
#include<algorithm>
using namespace std;

bool arr[100001];
int cnt,num;

int main() {
	int n, k, b;

	cin >> n >> k >> b;

	for (int i = 0; i < b; i++) {
		cin >> num;
		arr[num] = true;
	}

	for (int i = 1; i <=k; i++) {
		if (arr[i])
			cnt++;
	}

	int ans= cnt;

	for (int i = k + 1; i <= n; i++) { 
		if (arr[i])
			cnt++;
		if (arr[i - k])
			cnt--;

		ans= min(ans, cnt);
	}

	cout << ans;
	return 0;
}

메모리와 시간이 개선되었음을 확인할 수 있다.