[백준 / BOJ] 21319 챔피언(Easy)

문제

출처 : https://www.acmicpc.net/problem/21319

21319번: 챔피언 (Easy)

N명의 선수가 비 내림차순으로 주어진다.

각 선수는 자신의 양쪽선수와 경기를 하며 파워가 더 쌘 선수가 승리한다.

승리시 자신의 파워가 +1 증가하며, 패배한 선수의 양쪽 선수와 연결된다.

위 과정을 반복후, 경기장에 혼자 남아있을때, 그 선수를 챔피언 이라고 한다. 이때, 챔피언이 될 가능성이 있는 선수를 모두 구하는 문제다.

---

풀이 

그리디에 이분탐색으로 푼 문제다.

 

문제의 입력조건중, "모든 선수의 초기파워는 비내림차순이다"를 잘 생각해보면, 다음 조건을 유추할수있다.

 

1. i번째 선수는 i+1번째 선수보다 작거나 같다. 즉, i번째 선수가 i+1번째 선수를 이기기 위해선, i-1번째 선수보다 커야한다.

-> 따라서, i번째 선수가 i-1번째 선수와 크기가 같다면, i번째 선수는 절대로 챔피언이 될수없다.

-> 또한, 자신보다 적은 파워를 갖고(i-1번째이하 idx)있는 선수들과 먼저 경기해도 손해볼것이 없다.

 

2.. i번째 선수가 챔피언이 될수있다면, (N번째 선수까지 전부다 이길수있다면) i번째부터 N번째 선수는 모두 챔피언이 될수있다.

이는, 선수가 다른 선수에게 승리했을때 얻는 파워의 양과 관련이있다.

선수는 다른 선수에게 승리했을때 파워가 +1만큼 증가하지만, 입력으로 주어지는 수열은 파워가 +1이상 증가한다. (같은수가 입력될수있기때문에 +0이상 증가라고 생각할수있지만, 이는 자료저장방식을 적절히 바꾸며 예외처리해줄수있음)

-> 따라서, i번째 선수가 i+a번째에 도달했을때의 파워보다 i+a번째 선수가 i+a번째에 도달했을때의 파워가 항상 더 크거나 같다.

 

위 두가지 조건을 활용해서 이분탐색을 진행하면 된다. 그 전에 위에서 설명한 적절한 자료구조를 만들어 줘야하는데,

class{power의첫 등장 idx, power}와 같은 형태로 power의 중복을 없애며 저장해준다.

이렇게 저장할경우, 증가 수열이 되기때문에, 2번 조건을 항상 성립시킬수있다.

 

알고리즘

left = 1, right = size()-1

(left를 두번째 인덱스부터 시작하는 이유는 1번조건에 의해서, 첫번째 인덱스는 절대로 챔피언이 될수없기 때문임)

 

- mid(left + right / 2)인덱스에 있는 선수가 챔피언이 될수있는가?

yes -> right = mid (mid를 포함해, 더 적은 파워를 갖고있는 선수가 챔피언이 될 수 있는지 확인한다.)

no -> left = mid+1 (mid는 챔피언이 될수없으므로 포함하지않는다. 더 큰 파워를 갖고있는 선수가 챔피언이 될 수 있는지 확인한다.)

 

주요 소스코드

	private StringBuilder findChampion(){
		StringBuilder sb = new StringBuilder();
		if(!canWin(champions.get(champions.size()-1))){
			sb.append("-1");
			return sb;
		}
		int left = 1, right = champions.size()-1;
		while(left < right){
			int mid = (left+right)/2;
			if(canWin(champions.get(mid))) right = mid;
			else left = mid+1;
		}
		for(Champion champion : champions){
			if(champion.initIdx < startIdx) continue;
			sb.append(champion.initIdx);
			sb.append(" ");
		}
		return sb;
	}

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/21319%20%EC%B1%94%ED%94%BC%EC%96%B8/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃