백준 g4 13144 List of Unique Numbers c++

https://www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

 

문제

길이가 N인 수열이 주어지고, 이 수열에서 연속 부분 수열을 골랐을 때 겹치는 수가 없는 경우의 수 구하기

 

풀이

st를 0 ~ N-1까지 이동시키고, 각각의 경우마다 en을 움직일 수 있을 때까지 움직인다.

하나의 st당 경우의 수는 st ~ en의 개수가 되고, (ex. 1 ~ 5 면 1, 12, 123, 1234, 12345 총 5가지를 만들 수 있다)

하나의 st를 수행하고 난 후에는 st++로 한 칸 옮겨주면 된다. 어차피 st+1 ~ en간은 unique하므로, en을 앞으로 옮길 필요 없이 en+1부터 다시 옮길 수 있을 때까지 옮겨주면 된다.

 

수도 코드

for st: 0 ~ N-1
	//1. en을 움직일 수 있을 때까지 움직임
    while (en < N)
    	if en이 이미 있으면
        	break
        else
        	check[en] = true
            en++
    //2. ans에 더하기
    ans += (en - st)
    
    //3. st 한 칸 옮기기 전에 check 해제
    check[st] = false

 

전체 코드

/*boj g4 13144 List of Unique Numbers*/
#include <iostream>
#define MAXN 100005
using namespace std;

int N;
int a[MAXN];
bool check[MAXN];
long long ans = 0;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> a[i];

    int en = 0;
    for (int st = 0; st < N; st++) {
        // 1. en 움직일 수 있을 때까지 움직임
        while (en < N) {
            if (check[a[en]] == true) {
                break;
            } else {
                check[a[en]] = true;
                en++;
            }
        }
        ans += en - st;
        // cout << st << en << "\n";
        check[a[st]] = false;
    }

    cout << ans << "\n";
}