8/8 ~ 8/14 PS

BOJ 9007 - 카누 선수 (G3)

MITM 기초문제이다.

 

BOJ 9010 - Möbius Strip (G3)

가로와 세로를 따로 계산할 수 있다. 식 정리는 매우 깔끔하게 나온다.

 

BOJ 9011 - 순서 (G5)

R_n부터 거꾸로 돌아가며 배열을 채워주면 된다. N이 작아서 가능함

 

BOJ 22348 - 헬기 착륙장 (P4)

dp[r][a] = 반지름이 r이고 어떤 색의 페인트를 a만큼 사용했을 때의 경우의 수로 정의하자. 이 dp의 누적합을 또 만들어 주고 각 쿼리를 O(1)에 구하면 된다.

 

BOJ 1071 - 소트 (P5)

문제가 하라는 대로 O(N^2)로 풀면 된다. 단순 구현

 

BOJ 2320 - 끝말잇기 (G1)

dp[l][r][bit] = 왼쪽과 오른쪽에 l번째, r번째 string이 들어가 있고, 상태가 bit일 때의 문자열의 길이라고 정의하자. 문자열을 이어붙일 수 있을 때만 dp를 갱신하면 된다.

 

BOJ 16725 - 다항 계수 (P5)

https://www.secmem.org/blog/2019/10/19/generating-function/

생성함수를 공부하고 풀어본 문제다. 그냥 이런 게 있구나 하고 말았다..

 

BOJ 3121 - 빨간점, 파란점 (D3)

불도저 트릭 + 금광세그. 색에 따라 1, 0으로 구분하고 1로만 이루어진 연속 부분 수열의 최대 길이를 찾으면 된다.

 

BOJ 16601 - Access Points (D4)

1. x좌표와 y좌표를 따로 보는 것이 가능하므로, 1차원에서 생각해보자.
2. x좌표가 담긴 배열 A가 구간 [1, N]에서 단조증가한다면 답은 0이다. 문제는 감소하는 부분인데, 이를 어떻게 처리해야 할까?
3. (편의 상 문제의 그림대로 네모와 동그라미라고 함) 어떤 감소하는 구간을 담당하는 네모의 좌표를 x라고 하자. 이와 연결되는 동그라미들만 볼 때, cost = sum((x - A_i)^2)가 된다. 그리고 이를 최소화하려면 x는 담당하는 동그라미의 좌표의 평균이 되어야 한다.
4. Monotone Stack을 이용해 prev > now라면 전 구간과 합쳐주며 진행하면 된다. x, y 각각에 대해 진행하면 되고, O(N)에 문제를 풀 수 있다.

(슬랙에 올린 풀이)

 

BOJ 16603 - Circuit Board Design (P4)

처음 각도를 0으로 잡고 시작하자. dfs를 돌리면서, 각 부분의 dfs가 끝날 때마다 각도를 pi/1100 만큼 증가시켜주면 된다.

 

문제풀이의 재미를 다시 찾아가는 것 같아 기쁘다.