백준 12018번: Yonsei TOTO (Python/Java)

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

12018번: Yonsei TOTO

 

 

 

접근

---

문제를 보고 가장 먼저 생각한 것은 '현재 입력한 과목을 신청할 때, 내가 최소로 투자할 마일리지'였다. 마일리지를 최소로 사용해야 다른 과목에 투자할 마일리지가 많아지는 건 너무 당연한 사실이니까. 우선 내가 각 과목마다 투자할 '최소 마일리지 배열'을 만든 뒤 본격적으로 문제 풀이에 들어갔다.

 

문제 조건에 따르면 마일리지는 총 100점까지 주어진다. 즉, 학생들이 배팅할 마일리지의 최댓값은 100점이라는 것을 알 수 있다. 그렇다면 이제 같은 값을 배팅한 학생의 수를 확인해야 한다. 나는 0이 101개 들어간 배열을 사용해 학생수를 체크했다.(편의를 위하여 100번 인덱스까지 총 101개의 값을 가지는 배열을 만들어주고 0번 인덱스를 제외한 나머지 100개를 이용했다.) 이 배열의 각 인덱스는 배팅한 마일리지 점수, 해당 인덱스에 들어있는 값은 해당 마일리지에 배팅한 인원 수가 된다. 이제 마일리지 당 배팅한 인원이 몇 명인지 배열을 통해서 확인할 수 있다.

 

이때, 배팅한 인원이 총원보다 적다면 1점만 투자하면 되니 최소 마일리지 배열에 1을 추가한 뒤 빠져나온다.  만약 배팅한 인원이 총원보다 크거나 같다면 100점을 투자한 인원수부터 차례로 확인해본다. (100번 인덱스부터 거꾸로 배열을 탐색한다) 인원수가 총원을 넘어가는 순간의 인덱스 번호, 즉 마일리지 점수가 내가 해당 과목에 투자할 수 있는 최소 마일리지 점수다. 해당 마일리지 점수를 최소 마일리지 배열에 추가한다. 이를 과목 수만큼 반복한다.

 

이제 문제에서 고려해야 하는 두 번째 최적 선택이 나온다.(즉, 이 문제에서 확인해야 할 그리디 알고리즘의 최적 선택은 두 개다.) 바로 최소 마일리지 배열의 가장 작은 값부터 더하는 것이다. 작은 값부터 더해나가야 가장 많은 과목 수를 구할 수 있다는 것은 쉽게 파악할 수 있을 것이다.

 

최소 마일리지 배열을 작은 수부터 정렬하고 하나씩 더하기 시작한다. 더한 값들이 내가 가진 총마일리지보다 많아지면 바로 직전 과목 수, 같아지면 지금 과목수를 출력한다. 이렇게 하면 문제가 반 정도 해결된다.

 

위 과목수를 구하는 과정에선 모든 과목에 투자할 충분한 마일리지가 있을 때를 고려하지 않고 있다. 때문에 모든 과정이 끝난 뒤, 내가 가진 총 마일리지 수보다 모든 최소 마일리지 합이 작다면 총과목수를 출력하면 된다.

 

 

 

풀이

---

Python

subjectNum, mileageNum = map(int, (input()).split())

resultList = []
for i in range(subjectNum):
    subNum, fullNum = map(int, (input()).split())
    mileageList = (input()).split()
    
    scoreList = [0 for i in range(101)]
    for j in range(subNum):
        scoreList[int(mileageList[j])] += 1
        
    result = 0
    if subNum < fullNum:
        resultList.append(1)
    elif subNum >= fullNum:
        for j in range(100, 0, -1):
            result += scoreList[j]
            if result >= fullNum:
                resultList.append(j)
                break

resultList = sorted(resultList)
mileageSum = 0
result = 0
for i in range(subjectNum):
    mileageSum += resultList[i]
    if mileageSum > mileageNum:
        result = (i)
        break
    elif mileageSum == mileageNum:
        result = (i+1)
        break

if mileageNum > mileageSum:
    result = subjectNum

print(result)

 

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        
        String[] firstLine = (br.readLine()).split(" ");
        int subjectNum = Integer.parseInt(firstLine[0]), mileageNum = Integer.parseInt(firstLine[1]);
        
        int[] resultList = new int[subjectNum];
        for(int i = 0 ; i < subjectNum ; i++){
            String[] secondLine = (br.readLine()).split(" ");
            int subNum = Integer.parseInt(secondLine[0]), fullNum = Integer.parseInt(secondLine[1]);
            String[] mileageList = (br.readLine()).split(" ");

            int[] scoreList = new int[101];
            for(int j = 0 ; j < subNum ; j++){
                scoreList[Integer.parseInt(mileageList[j])] += 1;
            }

            int result = 0;
            if(subNum < fullNum){
                resultList[i] = 1;
            }else if(subNum >= fullNum){
                for(int j = 100 ; j > 0 ; j--){
                    result += scoreList[j];
                    if(result >= fullNum){
                        resultList[i] = j;
                        break;
                    }
                }
            }
        }

        Arrays.sort(resultList);
        int mileageSum = 0;
        int result = 0;
        for(int i = 0 ; i < subjectNum ; i++){
            mileageSum += resultList[i];
            if(mileageSum > mileageNum){
                result = i;
                break;
            }else if(mileageSum == mileageNum){
                result = (i+1);
                break;
            }
        }

        if(mileageNum > mileageSum){
            result = subjectNum;
        }

        br.close();
        bw.write(result + "");
        bw.flush();
        bw.close();

    }

}

 

 

 

후기

---

다른 사람들의 풀이를 읽어보지는 않았지만 우선순위 큐를 이용하는 방법을 통해 훨씬 효율적으로 풀 수 있다고 한다. 아무래도 배열을 이용해서 모든 경우를 파악하는 것은 비효율적인 방법이긴 하다. 특히, 이런 문제는 입력 값이 크지 않고 연산이 비교적 적었기 때문에 가능했지, 조건의 범위가 넓었으면 무조건 시간 초과가 났을 것이라 생각한다. 다시 한번 생각해보고 더 효율적인 방법을 생각해봐야겠다.