목록19951 (1)

그거 기능이에요

백준 19951 태상이의 훈련소 생활

문제 소개백준 19951 태상이의 훈련소 생활태상이는 훈련소에서 삽질을 하는데, 조교들이 각각 a 부터 b까지 무작위로 땅을 c칸 파라고 명령한다.여기서 c는 +일지 -일지 알 수 없기 때문에 태상이는 각 칸마다 최종 높이를 미리 계산해서 일을 한번에 하려고 한다.연병장의 크기와 조교의 명령 횟수는 각각 100,000이기 때문에 단순 완탐이 아닌 다른 방법으로 풀어내라접근 방법사실 이 문제 해결방법이 1시간 넘게 떠오르지 않아 다른 블로그의 풀이를 참고했다.내가 그동안 풀었던 누적합 문제는 내가 미리 누적합을 구해두고 연산할 때 활용하는 방식으로 연산수를 줄이는 방식이었다.하지만 이 문제는 마지막에 누적합을 수행했을 때 각 칸에서 최종적으로 몇 칸씩 더 파거나 더 쌓아야하는지 계산할 수 있도록 누적합을 ..
백준/오늘의 문제 2024. 12. 18. 14:56
이전 Prev 1 Next 다음