BOJ Random Defense - 3

 

9/9 ~ 10/11

 

 

BOJ 4167 - Tunnelling the Earth

Gold 3

Elapsed Time : --

Rating : 1224 -> 1208 (-16)

 

소수점 문제인 것을 보고 도망쳤다.

 

 

BOJ 10021 - Watering the Fields

Gold 3

Elapsed Time : 5m 36s

Rating : 1208 -> 1233 (+25)

#mst

 

좌표평면에서의 기본 MST 문제이다.

 

 

BOJ 7639 - Counting Pixels

Silver 1

Elapsed Time : 13m 16s

Rating : 1233 -> 1241 (+8)

#math   #geometry

 

답은 r값만으로 정해진다. 원의 방정식을 이용해서 구해주었다.

 

 

BOJ 26650 - 그램팬

Silver 1

Elapsed Time : 12m 33s

Rating : 1241 -> 1249 (+8)

#string

 

연속 여부와 A, Z인 경우만 잘 확인하며 구현해주면 된다.

 

 

BOJ 1368 - 물대기

Gold 2

Elapsed Time : 17m 49s

Rating : 1249 -> 1277 (+28)

#mst

 

분리 집합으로 물이 있는지 여부를 관리하며 mst를 구성하자.

 

 

BOJ 1677 - 음악

Gold 1

Elapsed Time : --

Rating : 1277 -> 1268 (-9)

 

???

 

 

BOJ 25580 - Next Level

Gold 2

Elapsed Time : --

Rating : 1268 -> 1255 (-13)

 

무서운 구현

 

 

BOJ 26455 - Pizza delivery

Gold 4

Elapsed Time : 21m 6s

Rating : 1255 -> 1272 (+17)

#greedy   #sorting

 

두 주문 중 어떤 것이 먼저 와야 이득인지를 부등식으로 나타내어 정렬 기준을 잡아주면 된다.

 

 

BOJ 30940 - Pingvin

Gold 5

Elapsed Time : 8m 46s

Rating : 1272 -> 1283 (+11)

#bfs

 

토마토 비스무리한 문제

 

 

BOJ 12499 - Revenge of the Hot Dogs (Small)

Gold 5
Elapsed Time : --

Rating : 1283 -> 1253 (-30)

 

소수점 == pass

 

 

BOJ 27928 - 단조 증가 수

Gold 1

Elapsed Time : 50m 47s

Rating : 1253 -> 1285 (+32)

#backtracking   #prefix_sum   #binary_search

 

$10^{18}$ 이하의 단조 증가 수의 개수는 $5\,000\,000$개 미만이다.다 구해서 누적합으로 $1$부터 $i$까지의 합을 저장해놓고 쿼리마다 이분 탐색 + 수학으로 답을 구해주자.