6/27 ~ 6/30 PS

이틀 뒤 UCPC다. 내일은 브론즈 하나만 풀고 잘 듯

 

 

BOJ 25223 - Reset (P5)

이분 탐색을 하면 된다. research를 어떤 task에 해야 하는지에 대한 아이디어를 떠올리는게 힘들었다. 필요한 리셋 횟수가 k일 이상이라면, 이 일을 어려운 일이라고 하자. 일단, 쉬운 일과 어려운 일들을 어떻게 해도 k일 내에(리셋은 k-1회) 끝낼 수 없다면 불가능한 경우이다. 그리고 k-1번의 리셋을 하고, 마지막 k번째 날에 해야하는 어려운 일의 시간들의 합이 c보다 크다면 불가능하다. 아니라면 가능함

 

BOJ 16225 - 제271회 웰노운컵 (D5)

B에 대해 정렬하면, 맨 왼쪽은 내가 항상 가져가게 된다. 인덱스가 작은 곳부터 2칸씩 늘리면서, 지금까지 본 것들 중 가장 A값이 높은 것을 가져가면서 밀면 된다.

 

BOJ 15769 - PuyoPuyo (P4)

뿌요를 세로로 떨어뜨린다는 아이디어는 금방 생각할 수 있다. 구현이 약간 까다롭다.

 

BOJ 8201 - Pilots (P4)

덱을 이용해 구간 최대/최소를 O(N)에 찾을 수 있고, inching worm을 통해 최대 구간을 찾을 수 있다. 난 덱 최대/최소를 이제야 알았다;;

 

BOJ 24231 - 해석 (G1)

dp[l][r]을 l~r에서 가능한 경우의 수라고 정의하고 풀면 된다. AxBy (A, B는 올바른 괄호 문자열이고, x, y는 길이가 1인 문자열)의 형태일 때, x != y인 경우에 나눠주면 된다.

 

BOJ 24232 - 망가진 나무 (G2)

간선에 대한 트리 dp이다. dfs를 하며 간선 방향이 바뀔 때 dp값에 변화를 주면 된다.

 

BOJ 24236 - 1차원 애니팡 (P2)

업데이트가 있다 = 세그를 쓴다. 어떤 구간의 왼쪽 부호를 \(l\), 오른쪽 부호를 \(r\)이라고 하면, 이 구간의 최소 비용은 \(dp[l][r] = \min_{0\leq k\leq 2}(L[l][k] + min(R[(k+1)\mod 3][r], R[(k+2)\mod 3][r]))\)가 된다. 구간의 길이가 1일 때에 주의하여 풀면 된다.

 

 

아래 3문제는 연습셋을 푼 건데, 3시간 동안 푸는게 되게 힘들었다..

ucpc화이팅!