[Java]BOJ 16112 : 5차 전직

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

🚩문제

🔓문제해결

1. 활성화된 스톤은 경험치가 0이 되고 활성화되어있는 스톤에 그 값이 더해진다.

2.최댓값을 구하려면 작은 경험치부터 활성화되어야한다.

=>활성화될때 경험치가 0이되니 모두 활성화가 되었을때 남아있는 스톤의 경험치가 클수록 좋기 때문이다.

=>활성화갯수가 최대가 되면 그 이후로 남은 스톤은 활성화갯수만큼 경험치가 더해진다.

---

참고 블로그 : https://blog.naver.com/hoo3164/222718534082

예를 들어 스톤 6개 , 최대 활성화 스톤 개수(3개)

1번째 활성화 ->영향받는 스톤x

2번째 활성화 ->영향받는 스톤1개

3번째 활성화 ->영향받는 스톤2개

4번째 활성화 -> 영향받는 스톤 3개

5번째 활성화 -> (2,3,4)번째활성화 된 스톤  =   영향받는 스톤 3개

6번째 활성화 -> (3,4,5)번째 활성화 된 스톤 = 영향받는 스톤 3개

---

우선순위 큐 시간 복잡도는 입력: O(log n), peek: O(1), poll: O(log n) 의 시간복잡도

3. 우선순위큐(A)에 경험치를 입력해준다

4.최대 활성화 스톤개수가 되기 전까지는 해당 값을 큐에서 빼내고 활성화 스톤 개수+1 해준다.

5.큐에서 빼낸 경험치 * 활성화스톤 개수를 결과값에 더해서 다른 큐(B)에 넣어준다.

6.최대 활성화 스톤 개수가 되면  큐에 남은 스톤의 경험치 * 최대활성화스톤개수 후 결과값에 더해준다

7.B에 저장된 경험치들을 결과값에 더해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
* 입력
경험치갯수n 최대활성화k
*
* 출력
경험치합의 최댓값
* */

* */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Long>pq = new PriorityQueue();
        PriorityQueue<Long>pq2 = new PriorityQueue();
        String [] str = br.readLine().split(" ");
        String [] str2 = br.readLine().split(" ");
        long n = Long.parseLong(str[0]); //경험치 수
        long k = Long.parseLong(str[1]); // 활성화 갯수
        long result = 0L;
        int cnt =0;
        for (int i = 0; i < n; i++) {
            pq.offer(Long.parseLong(str2[i]));
        }
        while (cnt<=k && !pq.isEmpty()) { //활성화 할때
            Long m = pq.poll();
            pq2.offer(m*cnt);
            cnt++;
        }

        while (!pq2.isEmpty()) { //활성화 되었던 스톤
            result += pq2.poll();

        }
        while(!pq.isEmpty()){ //남아있는 스톤
            result += pq.poll()*k;
        }

        System.out.println(result);

    }

}

메모리 : 72312KB, 시간 : 608ms

 

💊또 다른 풀이

1. 위에서 처럼 우선순위 큐로 접근하는 방법은 똑같다.

2.하지만 우선순위 큐 1개 +while+if문의 조합을 이용

3.while문을 돌며 큐의 값을 바로 계산해서 결과값에 더해준다.

   3-1 만약 활성화스톤갯수가 최대활성화 스톤개수가 되지않았다면 결과값에 꺼낸 경험치 * 활성화스톤갯수를 더하고

          활성화스톤갯수 +1 해준다.

   3-2 만약 활성화 스톤갯수와 같으면 꺼낸 경험치 * 활성화 스톤갯수만 해준다.

4.큐가 빈스택이 되면 값을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
* 입력
경험치갯수n 최대활성화k
*
* 출력
경험치합의 최댓값
* */

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Long>pq = new PriorityQueue();

        String [] str = br.readLine().split(" ");
        String [] str2 = br.readLine().split(" ");

        long n = Long.parseLong(str[0]); //경험치 수
        long k = Long.parseLong(str[1]); // 활성화 갯수
        long result = 0L; //결과값

        for (int i = 0; i < n; i++) {
            pq.offer(Long.parseLong(str2[i]));
        }

        pq.poll(); //스톤1개를 활성화
        int cnt =1; //현재까지 활성화된 스톤 갯수
//1개를 while문 밖에서 활성화 한 이유는 1개만 뽑았을때는 영향을 미치는 스톤이 없기때문이다
        while (!pq.isEmpty()) {
            if(cnt<k){
                result += pq.poll() * cnt;
                cnt++;
            }else {
                result+=pq.poll()*k;
            }
        }

        System.out.println(result);

    }

}

메모리 : 61216KB, 시간 : 556ms