[백준 01321] 군인 [Java]

문제

캠프 내내 그랬듯이, 여전히 옆 나라와의 전쟁이 한창이다.

전쟁에는 N개의 부대가 투입되었는데, 전쟁이 장기전이 되다 보니 군사의 적절한 배치를 위해 각 부대에 군인이 늘어나기도 하고 줄어들기도 하고 있다.

행정의 편의를 위해 각 군인들에겐 번호가 붙어 있는데, 군인들은 1번 부대부터 군번순서대로 차례차례 배치된다. 예를 들어 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 7명의 군인이 있다면 군번이 6번인 군인은 2번 부대에 배치되게 된다.

문제는 어떤 부대의 인원이 늘어나거나 줄어들었을 때 i번 군인이 어디에 배치되는지 인데, 이럴 때에는 군인도 군번도 처음부터 다시 배치하게 된다. 위의 예에서와 같이 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 7명의 군인이 있었는데, 1번 부대에서 3명의 감원이 일어난다면, 6번 군인은 3번 부대에 재배치 받게 된다.

전쟁 때는 부대의 감원과 증원이 많아 군사 재배치도 자주 일어나게 되는데, 이렇게 자주 배치가 바뀌자 군인들은 자기가 도대체 어떤 부대에 속하는 지 헷갈리게 되었다. 다행히도 바뀐 군번은 다들 정확하게 숙지하고 있다.

부대의 개수 N과 각 부대에 속해 있는 군인의 수가 N개 주어질 때, 부대의 감원과 증원을 한 후, 혹은 그 중에 군번 i번의 군인이 몇 번 부대에 속하는 지를 물어봤을 때, 그 질문에 대답을 해 줄 수 있는 프로그램을 작성하시오.

i번 부대에 증원이나 감원을 할 때엔 "1 i a"의 형태로 명령이 주어지고, 이는 i번 부대에 a명을 더한다는 뜻이다. 감원을 할 때엔 a가 0보다 작은 수로 주어진다. 감원을 해서 부대의 인원수가 0보다 작아지는 입력은 들어오지 않는다. a는 절댓값이 1보다 크거나 같고, 3,000보다 작거나 같은 정수이다.

군번 i번의 군인이 어떤 부대에 배치 받았는지 알고 싶을 때는 "2 i"의 형태로 명령이 주어지고, 이런 명령을 받았을 때는 i번 군인이 몇 번 부대에 배치 받았는지를 출력해야 한다. i는 전체 군인 수보다 작거나 같은 자연수이다.

입력

첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개수 M(1 ≤ M ≤ 10,000)개가 주어지고, 이어서 M줄에 걸쳐 명령이 주어진다.

출력

질문한 군인이 몇 번 부대에 배치 받았는지를 한 줄에 하나씩 출력한다.

---

풀이

최대 1000명의 군사가 있는 부대가 N개 있다.

군사들은 1번 부대부터 N번 부대의 인원까지 순서대로 군번이 부여된다.

자신의 부대 번호보다 작은 번호 부대의 증원 또는 감원에 따라 자신의 군번이 변동될 수 있다.

즉 군번이 몇번 부대에 있는지 찾는 문제는, 세그먼트 트리의 누적합에 대해 순서를 찾는 이분탐색 문제로 볼 수 있다.

 

update의 경우 누적합에 대한 세그먼트 트리이기 때문에,  유효한 범위에 대해 diff( =a )만큼 누적합을 갱신하자.

  

query의 경우 누적합에 대해 찾고자 하는 군번이 소속된 부대( start == end ) 까지 이분 탐색을 진행해주면 된다.

 

• 군번( target )이 왼쪽 누적합( tree[child] ) 이하인 경우 소속한 부대는 ( start ~ mid )중에 있을 것이고,
• 그렇지 않다면, 군번이 앞선 부대의 현인원보다 더 높기에 ( mid + 1 ~ end )의 부대에 대해 탐색해봐야 한다.
  단, 앞선 부대의 인원( 왼쪽 누적합, tree[child] )만큼 군번에서 감소시킨 후 탐색을 진행해주어야 한다.

 

탐색이 끝난 후 부대 번호( start  or end ) 반환하면 된다.

 

참고로 필자는 예비군이다. 

---

소스코드

보기

---

출처

1321번: 군인