[백준] 15565번: 귀여운 라이언 [C/C++]

# 문제

15565번: 귀여운 라이언
https://www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

 

---

# 접근

라이언 인형( = 1)이 k개 이상 있는 가장 작은 연속된 인형들의 집합을 찾아야 한다. 집합의 크기를 명시해 주지 않기 때문에, 이중 for문을 이용한 브루트 포스 식의 순회가 불가능하다(사실 가능하다 할지라도, N의 크기가 10⁶이기 때문에 시간복잡도에서 걸릴 것이다). 따라서 새로운 접근 방식을 생각해야 한다.

이럴 때 필요한 것이 바로 투 포인터 알고리즘이다. 투 포인터란 주어진 수열에서 특정한 성질을 가지는 부분 수열을 찾을 때 활용되는 방식으로, 각각 부분 수열의 처음과 끝을 나타내고 수열의 인덱스를 가리키는 변수 L과 R을 만들고 그 L과 R을 주어진 조건에 따라 움직여 가며 적절한 부분 수열을 찾아내는 알고리즘이다. L을 앞으로 한 칸 움직였다면 그만큼 합에서 빼고(시간복잡도: O(1)), R을 앞으로 한 칸 움직였다면 그만큼 합에 더하면(시간복잡도: O(1)) 된다. 이렇게 시간복잡도를 획기적으로 줄일 수 있는 기법이다.
(※ 시간복잡도 개념을 모른다면 그냥 코드가 얼마나 효율적으로, 빠르게 실행되는지를 나타내는 단위라고 생각하자.)
 
이 문제에선
1. 라이언 인형의 개수가 k보다 작다면 R 포인터를 한 칸 앞으로 당긴다.
2. 라이언 인형의 개수가 k보다 같다면(이 연산 과정을 따른다면 라이언 인형의 개수가 k보다 커질 수 없다.) 현재 부분 수열의 길이를 지금까지 기록된 최소 부분 수열의 길이와 비교한다. 그 다음 L 포인터를 한 칸 앞으로 당긴다.
3. 1과 2를 반복한다.
 
이 로직을 떠올리고 투 포인터 개념을 이용해 이를 구현하는 것이 핵심이다.

---

# 풀이

#include <stdio.h>
int main() {
  int arr[1000005];
  int n,k,length;
  int a=0;
  int b=0; //a = L포인터, b = R 포인터
  int min=2100000000;
  scanf("%d %d", &n, &k);
  for (int i=1;i<n+1;i++) {
    scanf("%d", &arr[i]);
  }
  
  arr[0]=0; //입력은 arr[1] 부터 받고, arr[0]은 0으로 남겨 계산이 좀 더 용이하도록 했다.

  
  int sum=0;
  while(1) {
    if(b==n+1) { //포인터 R이 끝에 도달한다면 반복 끝내기
      break;
    }
    if (sum == k) { //라이언 인형의 개수가 k인 경우
      length=b-a;
      min=(length<min)?length:min;
      a++; //나는 라이언 인형의 개수를 L 포인터가 가리키는 인덱스의 다음 인덱스 부터 세는 방식으로 구현했다.
      sum=(arr[a]==1)?sum-1:sum;
    }
    else { //라이언 인형의 개수가 k보다 작은 경우
      b++;
      sum=(arr[b]==1)?sum+1:sum;
    }
    
  }
  min=(min==2100000000)?-1:min;
  printf("%d", min);
}

나는 문제의 의도대로 충실하게 풀었으나, 라이언( = 1)인지 어피치( = 2)인지 구분하고 sum에서 더하고 빼는 것이 은근 까다롭고 실수가 많이 일어날 만한 부분이다. 이를 보완하기 위해 입력을 받을 때부터 1이라면 1로 입력받고, 2라면 0으로 입력받아 그냥 합 자체를 세는 것도 괜찮은 방식이라고 생각한다.