[BOJ] 1280

less than 1 minute read

나무 심기

1280번 https://www.acmicpc.net/problem/1280

anzandaa pick 문제입니다.

segment tree를 이용하는 문제입니다.
각 노드 번호를 좌표로 이용해줬습니다.

좌표 0, 4, 2에 나무가 하나씩 심어져있고, 이번에 좌표 3에 나무를 심는다면,
이번에 곱해줘야 하는 값은 (3 - 0) + (3 - 2) + abs(3 - 4) 입니다.

일반화하면,
이번에 심을 나무의 좌표 pos가 들어왔다면,
pos보다 왼쪽에 있는 나무들의 수와 합이 각각 l_cnt, l_sum이라고 하고,
오른쪽에 있는 나무들의 수와 합이 각각 r_cnt, r_sum이라고 했을 때,
이번에 곱해줘야 하는 값은 ((l_cnt * pos - l_sum) + abs(r_cnt * pos - r_sum)) % mod 입니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1280.cpp

Categories:

Updated:

Leave a comment