7/9 ~ 7/18 PS

골랜디.

 

BOJ 22345 - 누적 거리 (G2)

배열을 좌표 기준으로 정렬하고, 각 쿼리마다 이분 탐색을 통해 인덱스를 찾으면 된다. 누적 합을 사용해야 안 터짐

 

BOJ 16207 - 직사각형 (G2)

두 개씩 짝을 지을 수 있는 막대들을 긴 것부터 사각형을 만들면 된다.

 

BOJ 14941 - 호기심 (G2)

홀수 짝수 인덱스 누적 합 배열을 각각 만들어 주고, upper_bound로 소수 배열의 인덱스 구간$l$, $r$을 찾을 수 있다.

 

BOJ 2464 - 비밀번호 (G2)

코포 1A로 잘 나올 것처럼 생긴 문제다. 작은 수는, 가장 오른쪽의 '10'을 찾아서 '01'로 바꾼 다음, 이 뒤쪽에 나오는 1들을 왼쪽으로 싹 몰아주면 된다. 큰 수는 반대로 하면 된다.

 

BOJ 15053 - Buggy ICPC (P3)

모음인 알파벳이 나오면, 문자열은 뒤집히게 된다. 굳이 식으로 쓰자면 $S+a\to a+rev(S)$인데, 여기에서 또 모음이 나오면, S는 다시 뒤집히게 된다. $a+rev(S)+i\to i+S+a$ 즉, 모음이 앞, 뒤에 번갈아 붙는 것과 같다. 코너케이스에 유의하고, 초기의 '자음만 있는 문자열' S의 길이를 찾기만 하면 된다.

 

BOJ 22959 - 신촌 수열과 쿼리 (P4)

i가 구간 $[l,r]$에 포함되어야 하므로, 가능한 멀리 뻗어나가면 된다. 왼쪽과 오른쪽 각각에 대해 이분 탐색을 해주면 된다. $O(Nl{g}^{2}N)$

 

BOJ 14547 - 헤븐스 키친 (P5)

Maximum Spanning Tree를 만들고, 아무 정점에서 dfs를 돌리면서 정점을 지우면? 된다

 

BOJ 24496 - Drought (G2)

정방향으로, $A_i<A_{i+1}$인 경우에만 값을 변경해주고, 배열을 뒤집는다. 그러고 방금 한 것을 또 하면 된다.

 

BOJ 3090 - 차이를 최소로 (P2)

위와 같으나, 이분 탐색이 추가된 문제이다.