BOJ 17689 - Candies
boj 1150 - 백업 이랑 동일한 문제이다.
하지만 좀 더 구현법에 따라 까다로울 수 있다.
백업문제는 구간에 대해서 다루었다면 이건 점에 대해서 다루는 식이다.
백업문제는 세그먼트 트리로 풀었는데, 이건 DSU로 단순히 코드를 고쳐보았다.
캔디를 먹고와 못먹고를 0과 1로 나타내보면,
0 0 0 0 0 0 0 0
0 0 [0 1 0] 0 0 0
[0 1 0 1 0] 0 0 0
[0 1 0 1 0] 0 [0 1]
[1 0 1 0 1 0] [0 1]
뭐 대충 이런식으로 $1$이 생긴 구간의 양 옆의 $0$ 두 개를 이용해 구간을 확장해나가는 방식이다.
확장해나가다 다른 구간과 만나면 그 구간과 합쳐주는 테크닉을 DSU로 했고,
우선순위 큐에는 이번에 캔디를 하나 더 먹을 때, 증가하는 최대 값을 저장해야 한다.
이 값은 처음에 각 캔디 각각 모두이고,
$1$이 생긴다면 양옆의 $0$ 두개의 구간에 대해서 $0$과 $1$을 모두 반전시켜주는 값이다.
이건 또한 홀수와 짝수 따로 관리하는 prefix sum으로 관리할 수 있다.
Comments