DNA 비밀번호 (feat. 백준, 12891번)

DNA 비밀번호
https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
char arr[1000000];
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int S, P, A, C, G, T, A_cnt = 0, C_cnt = 0, G_cnt = 0, T_cnt = 0, l = 0, r, ans = 0;
    cin >> S >> P;
    for(register int s = 0; s < S; ++s)
        cin >> arr[s];
    cin >> A >> C >> G >> T;
    for(r = 0; r < P; ++r){
        if(arr[r] == 'A')       ++A_cnt;
        else if(arr[r] == 'C')  ++C_cnt;
        else if(arr[r] == 'G')  ++G_cnt;
        else                    ++T_cnt;
    }
    if(A_cnt >= A && C_cnt >= C && G_cnt >= G && T_cnt >= T)
        ++ans;
    while(1){
        if(r == S)
            break;
        if(arr[l] == 'A')       --A_cnt;
        else if(arr[l] == 'C')  --C_cnt;
        else if(arr[l] == 'G')  --G_cnt;
        else                    --T_cnt;

        if(arr[r] == 'A')       ++A_cnt;
        else if(arr[r] == 'C')  ++C_cnt;
        else if(arr[r] == 'G')  ++G_cnt;
        else                    ++T_cnt;
        ++l, ++r;

        if(A_cnt >= A && C_cnt >= C && G_cnt >= G && T_cnt >= T)
            ++ans;
    }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

P 범위의 윈도우가 우측으로 한칸씩 이동한다는 관점에서 본다면, 이동할때마다 Left 문자가 빠지고 Right 문자가 추가된다는 규칙이 있습니다.