백준 15565번 귀여운 라이언

www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

IDEA 

DP를 풀고나서 풀었더니 또 DP스럽게 생각을 하게 돼버렸다. 

난 초반에 문제 이해가 잘 안됐는데 문제 설명을 다시 해보자면 

K개 이상의 라이언 인형 = 1 을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력하는 문제다. 

-> 어차피 가장 작아야하므로 라이언 인형이 k개일때의 부분집합의 크기를 생각해주면 된다.

N= 10, K =3일 때,

1 2 2 2 1 2 1 2 2 1

이렇게 보면 라이언 인형이 3개인 부분집합의 크기는 7이다. 

1 2 2 2 1 2 1 2 2 1

하지만 이렇게 보면 부분집합의 크기는 6이므로 답은 6이 된다. 

 

K는 최대 1000000이기 때문에, 투포인터 같이 이중 for문을 사용하면 안된다고 생각했다.

그래서 nlogn 으로 풀 수 있는 방법을 생각하다가 또 이분탐색을 사용하는 LIS알고리즘 비슷하게 빠져버려따,,, 

1	2	2	2	1	2	1	2	2	1
1	1	1	1	2	2	3	3	3	4

 

• 인형이 1 즉 라이언 인형일 때는 DP값을 하나 더 해 업데이트해준다. -> 처음부터 몇 번째 라이언인지 저장 
  인형이 2 즉 라이언이 아닐 때는 이전 DP값을 사용한다. -> 이때까지 최대 라이언의 개수
  
  
• 만약 DP값이 K보다 크다면 이분탐색을 통해 K개 있는 구간을 구한다. 
  예를 들어 DP가 4인 경우 DP가 2인 곳을 찾아야 인형이 3개가 있다는 뜻이다. 
  그래서 이분탐색을 통해 DP=2이면서, 라이언인 곳을 찾아준다.
• 한 번도 이분탐색을 하지 않았다면 K보다 크거나 같은 라이언이 없었다는 뜻이므로 -1을 반환해준다. 

CODE

#include <iostream>
#include <vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>

using namespace std;

int doll[1000001] = { 0 };
int dp[1000001] = { 0 };

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, k , min_len = 1000001;
	bool stop = true;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> doll[i];
		if (doll[i] == 2) dp[i] = dp[i - 1] ;
		else {

			dp[i] = dp[i - 1] + 1;

		
			if (dp[i] >= k) {
				stop = false;
			//이분탐색을 통해 dp값이 dp[i] - k + 1인 인덱스를 찾는다. 
				int start = 0, end = i - 1, target = dp[i] - k + 1;
				while (start <= end) {
					int mid = (start + end) / 2;
					if (dp[mid] == target && doll[mid] == 1) {
						int len = i - mid + 1;
						min_len = min(min_len, len);
						//find = true;	
						break;
					}
					else if (dp[mid] > target || (dp[mid] == target && doll[mid] == 2))  end = mid - 1;
					else  start = mid + 1;
				}
			}
			
		}
	}
	if (!stop) cout << min_len;
	else cout << -1;
}

  돌아 돌아 푼 문제였다. 정답률을 보니 어려운 문제는 아닌 거 같은데 메모리나 시간이 엄청 많이 소요됐다. (C++치고)

 

남의 코드 

시간과 메모리를 절반 이하로 줄일 수 있는 코드를 발견 분석해보자.

큐를 쓸 생각을 하다니,,,,, ㅜㅜ,,,,,

1 ~ K , 2 ~ K+1개 이런 식으로 앞에서는 하나가 나가고 뒤로는 하나가 들어오는 구조니 큐를 사용하는 게 생각해보면 당연하다,,,,

큐에는 딱 K개만 들어갈 수 있도록 코드를 짜놨다. 

1이라면 인덱스를 큐에 넣고 , 큐의 사이즈가 K가 됐다면 부분집합의 구간을 구할 수 있단 얘기이므로, 맨 앞에 있는 인형의 인덱스 , 맨 뒤의 있는 인형의 인덱스를 구해 길이를 업데이트해준다. 

이후 다음 인형이 들어오기 위해서는 하나가 빠져줘야하므로 POP을 해준다,

개쩐다......

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int N,K,answer=1<<20;
    char doll;
    queue<int> Q;
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>doll;
        if(doll=='1'){
            Q.push(i);
            if(Q.size()==K){
                answer=min(answer,Q.back()-Q.front()+1);
                Q.pop();
            }
        }else if(doll==' ') i--;
    }
    cout<<(answer==(1<<20)?-1:answer);
    return 0;
}

ㅁ