값 / 좌표 압축1 [백준] 2517: 달리기 - JAVA https://www.acmicpc.net/problem/2517 풀이N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때, 실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다. 예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다. 10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다. 세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다. 1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다. 구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다. 각 선수의 실력은 모두 다르므로 .. 2024. 5. 18. 이전 1 다음