백준 21695 - Школа танцев (C++)

문제

• 문제 링크

  
   BOJ 21695 - Школа танцев 
  

• 문제 요약

남학생, 여학생이 구분 없이 일렬로 서있다.
남학생과 여학생의 수가 같은 부분 일렬의 수를 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N ≤ 10^6$

알고리즘 분류

• 자료 구조(data structures)
• 해시를 사용한 집합과 맵(hash _ set / map)
• 누적 합(prefix_sum)

풀이

두 가지의 상태가 동일한 비율인 연속 부분 수열의 개수를 세야 한다.

결국 $a = 1, b = -1$ 로 가중치를 메길 때, 이 문제 에서 $K = 0$ 일 때로 환원 시킬 수 있다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
unordered_map <ll, int> M{{0, 1}};
ll n, r, s;
 
int main()
{
    cin >> n; getchar();
    for(char c; n--; M[s]++)
    {
        scanf("%c", &c);
        s += c & 1 ? 1 : -1;
        r += M[s];
    }
    cout << r;
}

comment

끝