[백준 / BOJ] 16564 히오스 프로게이머 (누적합 풀이)

문제

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

16564번: 히오스 프로게이머

N개의 캐릭터로 이루어진 팀이 있다. 이 팀의 팀 레벨은 팀의 가장 작은 레벨을 갖고있는 플레이어의 레벨과 동일하다. 

팀의 플레이어의 레벨을 K만큼 올릴 수 있을때, 최대 팀 레벨을 구하는 문제다.

---

풀이

약간의 아이디어만 있으면 풀리는 문제였다.

N과 K의 값이 커서 완전탐색으로 풀경우 시간초과가 나온다. 시간을 줄이기 위해서 누적합을 이용했는데, 아이디어는 다음과 같다.

 

"만일 팀 내의 플레이어의 레벨이 모두 같을경우, 팀 레벨을 올리기 위해선 모든 플레이어의 레벨을 똑같이 증가시켜줘야 한다."

따라서, 팀 내의 플레이어의 레벨을 모두 같게 설정하기만 하면, 팀 레벨은 아래와 같은 수식으로 한번에 구할 수 있다.

 

[팀 내의 레벨이 같은 임의의 플레이어의 레벨] + [K / 레벨이 같은 플레이어의 수];

하지만, 팀의 각 플레이어의 레벨을 모두 동일하게 설정하기에 K의 값이 부족할수도 있다. 따라서, 누적합을 이용해 레벨을 동일하게 설정해줄수있는 최대 범위를 구한후, 위의 연산을 진행해주면된다.

 

레벨을 동일하게 설정해줄수있는 최대 범위를 구하는 소스코드

	private int getMaxFairLevelIdx(){
		int spendedLevelUp = 0;
		for(int i = 1; i < this.levels.length; i++){
			spendedLevelUp += i*(this.levels[i] - this.levels[i-1]);
			if(spendedLevelUp == this.levelUp) return i;
			if(spendedLevelUp > this.levelUp) return i-1;
		}
		if(spendedLevelUp == 0) return 0;
		return this.levels.length-1;
	}

(0)번플레이어 부터 (i-1)번째 플레이어의 레벨을 (i)번째 플레이어와 동일하게 설정해주기 위해선, levelUp을 (i)번 진행해줘야함을 잊지말자.

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/16564%20%ED%9E%88%EC%98%A4%EC%8A%A4%20%ED%94%84%EB%A1%9C%EA%B2%8C%EC%9D%B4%EB%A8%B8/Main.java

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