23 Aug 2020

[BOJ 2370]

시장선거 포스터

문제 바로가기 : https://www.acmicpc.net/problem/2370
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution


review

Lazy propagation 안 써도 되는 문제 문제집에 있는 첫 번째 문제다.
포스터를 겹쳐 붙일 수 있으며 모든 포스터를 붙인 후에 보이는 포스터의 종류를 출력하면 된다.

처음엔 Lazy propagation을 안 써도 된다고 해서 그럼 세그먼트 트리까지는 사용해도 되는건가? 하고 접근을 해보려다가
구간에 업데이트를 해줘야 하기도 하고 또 구간 업데이트를 하자니 lazy를 써야할 것 같고해서 그냥 세그먼트 트리를 안썼다.
좌표 범위가 넓은거 같아서 좌표 압축을 해준 후 진행했다.
식별만 하면 되는 문제니까 그때 그때 다른 값이 나오면서 + 체크되지 않은 값이면 답을 갱신해줬다.

int ret = 1; int flag = arr[0];
chk[flag] = true;
for (int i = 1; i < 2 * n; i++) {
    int cur = arr[i];
    if (flag != cur && cur && !chk[cur]) ret++;
    chk[cur] = true;
    flag = cur;
}

Location

Icheon, KR

Email

iteratively@naver.com

Social

-->