금고털이

작성일: 2024-10-31

문제 링크 : https://softeer.ai/practice/6288

접근 방식

무게와 무게당 가격을 담은 배열을 만든다.

무게당 가격을 기준으로 배열을 내림차순 정렬한다.

무게당 가격이 높은 것부터 담아서 배낭을 채운다.

잘못된 접근

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt(); // 배낭 무게
        int N = sc.nextInt(); // 귀금속 종류
        int arr[][] = new int[N][2];
        for(int i=0; i<N; i++){
            int M = sc.nextInt();
            int P = sc.nextInt();
            arr[i][0] = M; // 총 무게
            arr[i][1] = P; // 무게당 가격
        }
        Arrays.sort(arr, (a, b) -> b[1] - a[1]); // 무게당 가격 기준 내림차순
        int answer = 0;
        for(int i=0; i<N && W>0; i++){
            if (arr[i][0]<W){
                W-=arr[i][0];
                answer+=arr[i][0]*arr[i][1];
            } else{
                answer+=W*arr[i][1];
                W=0;
            }
        }
        System.out.println(answer);
    }
}

시간초과가 났다.

잘 된 접근

입력받는 부분을 BufferedReader와 StringTokenizer로 변경했다.

결과

소스 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int W = Integer.parseInt(st.nextToken()); // 배낭 무게
        int N = Integer.parseInt(st.nextToken()); // 귀금속 종류
        int arr[][] = new int[N][2];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int P = Integer.parseInt(st.nextToken());
            arr[i][0] = M; // 총 무게
            arr[i][1] = P; // 무게당 가격
        }
        Arrays.sort(arr, (a, b) -> b[1] - a[1]); // 무게당 가격 기준 내림차순
        int answer = 0;
        for(int i=0; i<N && W>0; i++){
            if (arr[i][0]<W){
                W-=arr[i][0];
                answer+=arr[i][0]*arr[i][1];
            } else{
                answer+=W*arr[i][1];
                W=0;
            }
        }
        System.out.println(answer);
    }
}

알게 된 점

없음.