[3895] 그리고 하나가 남았다

https://www.acmicpc.net/problem/3895

3895번: 그리고 하나가 남았다

세그먼트 트리 문제다. 금방 풀 수 있을줄 알고 접근했는데, 생각보다 오랜시간이 소요됐다.

 

풀이

1부터 n까지의 숫자가 몇개가 있는지를 나타내는 세그먼트 트리를 구현. 남아있는 숫자중 x번째 수를 반환하는 함수와 구간별 숫자의 갯수를 반환하는 함수를 구현하여 접근하였다.

 

k번째 돌이라는 의미는 이전에 치워진 돌부터 시작하여 k%(현재 남아있는 돌의 갯수)번째 돌을 의미한다. 즉 치워진 돌 앞에 몇개의 돌이 있는지 정보를 가지고 있어야 한다는 점이다. 따라서 치워진 돌 앞의 돌의 갯수를 cnt라고 정의할 때, 우리는 (k+cnt)%현재 남아있는 돌의갯수 번째의 돌을 치우면 된다.

 

예제 "8 5 3"을 기준으로 다음과 같은 시나리오를 그릴 수 있다.

초기 상태의 구간 합 세그먼트 트리 생성

가장 먼저 m번째 돌인 3번 돌을 제거. 앞에는 두개의 돌이 있다. 

k + cnt % 남아있는 돌의 갯수. 즉 5 + 2 % 7 계산을 통해 0번째 돌을 제거해야하는데, 모듈러 계산에 의한 순서이므로 마지막 돌, 즉 일곱번 째 돌인 8번 돌을 제거하면 된다. 이때 앞에 남아있는 돌의 갯수는 6개가 된다.

6 + 5 % 6 계산. 5이므로 다섯번째 돌인 6번 돌을 제거한다. 

앞순번에 다섯번째 돌을 제거했기에 4 + 5 % 5 계산, 4번째 돌인 5번 돌 제거

다음으로는 3 + 5 % 4 계산, 4번째 돌인 7번 돌 제거

3 + 5 % 3 계산, 남아있는 돌 중 2번째 돌 2번 돌을 제거한다.

1 + 5 % 2 계산, 0번째 돌 즉 남아있는 마지막 돌인 4번 돌 제거.

마지막으로 1 + 5 % 1 계산, 0번째 즉 남아있는 마지막 돌 1번 돌이 제거된다.

마지막으로 제거된 1을 출력하면 정답이다.

 

정답 코드