5/24 PS

과제 이슈때문에 골드 이하로만 풀었다. 근데 왜이리 어렵지?

 

 

BOJ 24270 - 미니 버킷 리스트 (G4)

이게 골4 난이도인지는 잘 모르겠다. $(N+1)$개의 구간에 아무것도 안 하는 단위시간 $K-sum(S)$개를 채우는 문제이고, ${}_{N+1}{H}_{K-sum(S)}{=}_{N+K-sum(S)}{C}_N$을 계산하는 문제가 된다.

 

 

BOJ 24269 - 랜드마크 건설 (G2)

Case Work. 직사각형의 테두리에 건물 3개를 짓는 것으로 접근하면 된다. 직사각형의 가로와 세로의 길이는 $\frac{a+b+c}{4}$를 올림, 내림한 값으로 정할 수 있다.

 

 

BOJ 16681 - 등산 (G2)

보자마자 다익스트라 문제인건 알았는데, 무지성으로 다익스트라를 돌리면 (답이 음수일 수 있기 때문에) 안 된다. 1번 정점에서 모든 정점으로의 최단거리와 n번 정점에서 모든 정점으로의 최단거리를 기록해두자. 다만, 높이가 올라가는 경우에만 거리를 갱신해야 한다. 1 -> i -> n의 등산의 가치는 $H_i\ast e-d\ast (f(1,i)+f(n,i))$가 된다. f(x, y)는 x에서 y까지의 최단거리이다.

 

 

BOJ 3097 - 산책 경로 (S4)

문제가 시키는 대로, 그냥 $O(N^2)$로 구현하면 된다.

 

 

BOJ 17400 - 깃발춤 (P5)

전체 구간합과, 홀수 부분 구간합을 세그트리로 관리해주면 된다. 그러면 답은 $|Se{g}_{all}-2\ast Se{g}_{odd}|$ 가 된다.

 

 

혹시라도 고민하던 문제의 답을 본의 아니게 알아버리는 불상사가 있을 것 같아서 (나는 당한 적이 있다) 접은 글로 해놨다.