[BOJ 14465] 소가 길을 건너간 이유 5 C++ 풀이 // 슬라이딩 윈도우 설명

역사적인 첫 글!

 

문제 링크

www.acmicpc.net/problem/14465

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

소가 길을 건너간 이유 5 성공출처다국어분류

시간 제한 2 초

메모리 제한 512 MB

제출 848

정답 451

맞은 사람 394

정답 비율 52.815%

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

 

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

출력

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

 

풀이

문제의 핵심은 연속한 K개의 신호등이 존재하도록 수리하는 것 이므로, 1번 신호등부터 N번 신호등을, K길이 만큼만 탐색하여 몇 개가 고장났는지 세고, 최소 개수를 출력하는 문제입니다.

 

예제 입력을 예시로 설명을 이어나가겠습니다.

예제입력	예제 출력
10 6 5 2 10 1 5 9	1

10개의 신호등이 있고, 6개의 연속한 정상 신호등을 만드려고 하며, 5개의 고장난 신호등을 받아왔습니다.

이를 그림으로 표현하여, 아래와 같이 나타내었습니다. 빨간색은 고장난 신호등, 검정색은 정상 신호등입니다.

예제 입력을 그림으로 나타내었다.

우리는 K개의 연속한 신호등을 만들어야 하므로, 1번 신호등부터 K개의 신호등을 검사하여 몇 개가 고장났는지 세어야 합니다. 즉 파란색 칸 범위만큼 검사하여, 몇 개의 신호등이 고장났는지 체크합니다.

고장난 신호등은 3개이다.

고장난 신호등은 2개이다.

고장난 신호등은 1개이다.

위와 같이 일정한 범위를 옆으로 밀어가면서 탐색하여, 고장난 최소 개수를 찾으면 되는 문제입니다.

위와 같이 일정한 크기의 범위를 밀어가면서 탐색하는 방법을 슬라이딩 윈도우(Sliding Window)라고 합니다.

 

 

이를 C++코드로 간단하게 구현하면,  O(N^2)의 시간복잡도로 구현할 수 있습니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N, B, K;
bool map[100001];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
    
	int now;
	int ans = 100000;
    
    // 신호등의 고장을 기록할 map을 false로 초기화하여, 고장나지 않았음을 기록
	memset(map, false, sizeof(map));
    
	cin >> N >> K >> B;
    
    // B개의 고장난 신호등의 인덱스를 받아, map이라는 변수에 고장났다면 true로 갱신.
	for (int i = 1; i <= B; i++) 
	{
		cin >> now;
		map[now] = true;
	}
    
	for (int i = 1; i <= N - K + 1; i++)
	{
		int how_many_broken = 0;
        
        // 현재 i부터, 연속된 K개까지 확인하는 for loop
		for (int j = i; j < i + K; j++)
		{
        	// 만약 ,현재 신호등이 고장났다면 고장개수를 추가.
			if (map[j] == true)
				how_many_broken++; 
		}
        
        // 현재 고장난 신호등 개수와, ans를 비교하여 작은 것을 답으로 갱신합니다.
		ans = min(how_many_broken, ans); 
	}
	cout << ans;
}

 

 

이를 조금 더 최적화하면 O(N)의 시간복잡도로 풀이할 수 있습니다.

#include <iostream>
#include <algorithm>
#include <cstring>

//전역변수
int N, B, K;
bool map[100001];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); //입력 속도 향상
    
	int now;
	int ans = 100000;
    
 	// map배열을 false값으로 초기화
	memset(map, false, sizeof(map));
    
	cin >> N >> K >> B;
	
	// B개의 고장난 신호등의 인덱스를 받아, map이라는 변수에 고장났다면 true로 갱신.
	for (int i = 1; i <= B; i++) 
	{
		cin >> now;
		map[now] = true;
	}
	int cnt = 0;
    
	// 1번 신호등부터 K번 신호등까지 몇개가 고장났는지 확인.
	for (int i = 1; i <= K; i++)
		cnt += map[i];
	ans = cnt;
	
	int j = 1;
	for (int i = K + 1; i <= N; i++)
	{
    	// 인덱스를 하나씩 밀어가며, 슬라이딩 윈도우의 가장 앞, 뒤만을 갱신하여 빠른 처리.
		cnt += map[i];
		cnt -= map[j++];
		ans = min(ans, cnt);
	}
    
	cout << ans << '\n';
}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.