백준 2217번 : 로프 (시간초과 해결과정)

---

문제 이해하기

(예시가 하나밖에 없어서 이해하기 어려웠다..)

서로 다른 중량의 로프는 1개만 존재한다. 편하게 kg으로 생각해보자

10kg만큼 들 수 있는 로프가 1개, 15kg만큼 들 수 있는 로프가 1개이다.

10kg로프는 8kg을 들 수 있지만 12kg은 들 수 없다.

 

10kg과 15kg을 함께 사용할 떄,

15kg로프는 12kg을 들 수 있지만, 10kg로프는 12kg을 들 수 없다! 

▶ 결국엔 10kg 2개까지만 들 수 있다는 것이다.

 

예를 하나 더 들어보자

[8, 12, 5, 20, 4, 30] 총 6개 로프가 있다.

가장 높은 중량을 들기위해선 가장 높은 로프부터 선택해야한다

 

내림차순 정렬 : [30, 20, 12, 8, 5, 4] 

30 로프 사용 시 최대중량은 30

30+20 로프 사용 시 최대중량은 20+20 = 40 ⭐최대값

30+20+12 로프 사용 시 최대중량은 12+12+12 = 36

30+20+12+8 로프 사용 시 최대중량은 8+8+8+8 = 32

30+20+12+8+5 로프 사용 시 최대중량은 5+5+5+5+5 = 25

30+20+12+8+5+4 로프 사용 시 최대중량은 4+4+4+4+4+4 = 26

▶ N로프 사용 시 최대중량은 N*선택한순서

 

코드

import java.util.Scanner;

class Rope {
    int ropecount;
    int[] ropes;

    void scan_input(String inputed) {
        InputStream in = new ByteArrayInputStream(inputed.getBytes());
        System.setIn(in);
    }

    void scan() {
        Scanner scan = new Scanner(System.in);
        ropecount = scan.nextInt();
        ropes = new int[ropecount];
        for (int i = 0; i < ropes.length; i++) {
            ropes[i] = scan.nextInt();
        }
        scan.close();
    }

    void process() {
    
        //정렬
        int temp = 0;
        for (int i = 1; i < ropes.length; i++) {
            for (int j = 0; j < i; j++) {                       
                if(ropes[j] > ropes[i]){                        
                    temp = ropes[i];
                    for (int k = i; k > j; k--) {
                        ropes[k] = ropes[k-1];
                    }
                    ropes[j] = temp;
                }
            }
        }

		//최대값 확인
        int max = ropes[0] * (ropes.length);
        for (int i = 1; i < ropes.length; i++) {
            ropes[i] = ropes[i] * (ropes.length-i);
            if(max < ropes[i]){
                max = ropes[i];
            }
        }

        System.out.println(max);
    }
}

public class Main {
    public static void main(String[] args) {
        Rope r = new Rope();
        r.scan();
        r.process();
    }
}

 

위 코드의 결과는

 

혹시 Scanner때문인가.. 해서 다시 풀어봤다

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

class Rope {
    int ropecount;
    int[] ropes;

    void scan_input(String inputed) {
        InputStream in = new ByteArrayInputStream(inputed.getBytes());
        System.setIn(in);
    }

    void scan() throws IOException {
//        Scanner scan = new Scanner(System.in);
//        ropecount = scan.nextInt();
//        ropes = new int[ropecount];
//        for (int i = 0; i < ropes.length; i++) {
//            ropes[i] = scan.nextInt();
//        }
//        scan.close();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        ropecount = Integer.parseInt(st.nextToken());
        ropes = new int[ropecount];
        for (int i = 0; i < ropes.length; i++) {
            st = new StringTokenizer(br.readLine());
            ropes[i] = Integer.parseInt(st.nextToken());
        }
    }

    void process() {
    
        //정렬
        int temp = 0;
        for (int i = 1; i < ropes.length; i++) {
            for (int j = 0; j < i; j++) {                       
                if(ropes[j] > ropes[i]){                        
                    temp = ropes[i];
                    for (int k = i; k > j; k--) {
                        ropes[k] = ropes[k-1];
                    }
                    ropes[j] = temp;
                }
            }
        }

		//최대값 확인
        int max = ropes[0] * (ropes.length);
        for (int i = 1; i < ropes.length; i++) {
            ropes[i] = ropes[i] * (ropes.length-i);
            if(max < ropes[i]){
                max = ropes[i];
            }
        }

        System.out.println(max);
    }
}

public class Main {
    public static void main(String[] args) {
        Rope r = new Rope();
        try {
            r.scan();
        } catch (IOException e) {
            e.printStackTrace();
        }
        r.process();
    }
}

과연 결과는?!

 

이제 예상해볼수있는건 정렬시간 뿐이다....

정렬하는 과정이 문제의 의도라고 생각했는데..?????

확인을 위해 Scanner로 다시 돌려보겠다

package BJ211024_2217;

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

class Rope {
    int ropecount;
    int[] ropes;

    void scan_input(String inputed) {
        InputStream in = new ByteArrayInputStream(inputed.getBytes());
        System.setIn(in);
    }

    void scan() throws IOException {
        Scanner scan = new Scanner(System.in);
        ropecount = scan.nextInt();
        ropes = new int[ropecount];
        for (int i = 0; i < ropes.length; i++) {
            ropes[i] = scan.nextInt();
        }
        scan.close();

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine());
//
//        ropecount = Integer.parseInt(st.nextToken());
//        ropes = new int[ropecount];
//        for (int i = 0; i < ropes.length; i++) {
//            st = new StringTokenizer(br.readLine());
//            ropes[i] = Integer.parseInt(st.nextToken());
//        }
    }

    void process() {
        //정렬
//        int temp = 0;
//        //System.out.println(Arrays.toString(ropes));
//        for (int i = 1; i < ropes.length; i++) {
//            for (int j = 0; j < i; j++) {                       //System.out.print("key="+ropes[i]+" vs ropes["+j+"]="+ropes[j]);
//                if(ropes[j] > ropes[i]){                        //System.out.print(" insert  ");
//                    temp = ropes[i];
//                    for (int k = i; k > j; k--) {
//                        ropes[k] = ropes[k-1];
//                    }
//                    ropes[j] = temp;
//                }
//                //System.out.println();
//                //System.out.println(Arrays.toString(ropes));
//            }
//            //System.out.println();
//        }

        Arrays.sort(ropes);

        int max = ropes[0] * (ropes.length);
        for (int i = 1; i < ropes.length; i++) {
            ropes[i] = ropes[i] * (ropes.length-i);
            if(max < ropes[i]){
                max = ropes[i];
            }
        }
        System.out.println(max);
    }
}

public class Main {
    public static void main(String[] args) {
        Rope r = new Rope();
        r.scan();
        r.process();
    }
}

 

아.. 정렬시간이 문제였다!

정렬방법의 시간복잡도를 찾아보게 해준 문제였다

나중에 정리해봐야겠당