[HackerRank] Luck Balance

Practice > Algorithms > Greedy > Luck Balance

code

int luckBalance(int k, vector<vector<int>> contests) {
    int sum = 0;
    sort(contests.begin(), contests.end(), greater<vector<int>>());
    
    for(int i=0; i<contests.size(); i++){
        if(contests[i][1] != 0 && k>0){
            k--;
            sum += contests[i][0];
        }
        else if(contests[i][1] == 0)
            sum += contests[i][0];
        
        else
            sum -= contests[i][0];
        
    }
    return sum;
}

• 최대한 남은 행운 포인트를 높게 만드는 문제이다. 규칙은 이기면 필요한 행운 포인트만큼 차감하고 지면 필요한 행운 포인트만큼 더해준다. 이때 중요도가 1인 것은 k만큼 경기에서 질 수 있다. (중요도 1 - k 수만큼 꼭 이겨야 함)
• 따라서 내림차순으로 정렬을 한 뒤, 중요도가 1이고 k가 0보다 크면 k를 감소시키고 행운 포인트를 증가시켰다.
• 중요도가 0인 것은 져도 상관없는 경기이므로 모두 행운 포인트를 더하였고 중요도는 1이지만 져도 괜찮은 수가 남아있지 않다면 어쩔 수 없이 경기에서 이기고 행운 포인트를 차감했다.

결과