백준 8726 Dziewczynki [c++]

18 Jun 2022 in Develop / Solving

익이게 어느나라 언어입니까ㄷㄷ

문제 분석

• 뭐야 이게 무슨 언어야
• 입출력을 보고 감으로 한번 풀어보겠습니다.

구글 번역으로 문제 해석하여 문제 설명 추가합니당.

문제

소년, 소녀들이 줄을 서 있다. 이 중에 k명의 소녀가 연속해서 서 있게 하려고 할 때, 줄에서 빼내야 하는 소년의 수는 얼마인가.

입력

첫 번째 줄에 두 개의 정수 n, k (1 <= k <= n <= 10^6) 이 입력된다. n은 줄을 서있는 학생의 총 수이며, k는 연속해서 있게 하려는 소녀의 수 이다.

그 다음 줄에는 n개의 정수(0 1) 가 공백을 두고 입력된다. 이 중 0이 소녀, 1이 소년을 의미한다.

출력

첫 줄에 빼내야 하는 소년의 최소 수를 출력한다.

입력조건

숫자의 수 N 목표값 k
N개의 숫자

풀이과정

• 투포인터
• 포인터1(L)을 0의 위치까지 땡겨 오고, 거기서부터 소녀를 k개 잡을 때까지 포인터2(R)를 이동시킨다.
• 그러고 나서 그 사이에 있는 소년의 수를 세어서 정답과 비교하여 최솟값 저장.
• 위 과정을 r이 n에 도달할 때 까지 반복한다.

추가

시간초과를 꽤 많이 봤다. c++어렵다…

전체 코드

#include <iostream>

using namespace std;

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

    int n, k;
    cin >> n >> k;
    
    int arr[n];
    for(int i = 0; i < n; i++){ cin >> arr[i]; }
    
    int l = 0;
    int r = 0;

    int ans = 10000000;
    int girlcount = 1 - arr[0];

    while(r < n) {
        while(arr[l] == 1) {
            girlcount -= 1 - arr[l++];
        }
        while(girlcount < k && r < n) {
            girlcount += 1 - arr[++r];
        }

        if(girlcount == k){
            ans = min(ans, (r-l+1)-k);
            cout << l << " " << r << + " " << ans << endl;
            girlcount -= 1 - arr[l++];
        }
    }
    if(ans == 10000000) cout << "NIE";
    else                cout << ans;
}

추가

• 문제가 폴란드어로 되어있다…
• 내가 풀기 전에 정답이 12, 정답률 35퍼였는데,
• 내가 화나서 찔끔찔끔 바꾸면서 시간초과를 계속 보는 바람에 문제 정답률이 22퍼까지 떨어졌다…
• 뭔가 죄지은 기분…