백준 2243번 사탕상자 - 스위프트(Swift) 풀이

 CLASS 6 따기 중인데, 이제 3문제 밖에 안 남았다:)

 

 세그먼트 트리 문제. 구간합 문제라 더 구현이 간단한 펜윅트리로 풀었다. 펜윅트리 구현만 할 줄 알면 단순 적용만 하면 된다. 플래티넘 5 문제 중에는 이렇게 조금 난이도 있는 자료구조/알고리즘을 단순 적용하는 문제들이 꽤 있다.

 

 사탕들은 아래와 같이 관리한다. 

candy[i] = 맛 순위가 i인 사탕 개수

 

 먼저 n번째 사탕을 찾을 때를 보면, n번째로 맛있는 사탕의 맛 순위는 candy[1...k]의 구간합이 최초로 n이상이 되는 k(lower bound)가 된다. 사탕을 넣거나 뺄 때는 candy[i]에 원하는 개수만큼을 더하거나 빼면 된다. 이렇게 계속 변화하는 배열의 구간합을 구해야 하므로, 펜윅트리를 쓸 수 있다.