백준 2217 - 로프 (Java)

 

문제 개요

 

문제 개요 + 예시 입출력

 

---

 

풀이

 

전체 로프의 정보가 주어질 때 해당 로프들로 들 수 있는 최대 중량을 구해야 한다.

 

문제에서 원하는 값을 구하기 위해 생각했던 최초의 방법은 각 로프들 중 최소의 중량을 가지는 로프를 구한 뒤, 해당 로프의 중량에 전체 로프의 수를 곱하여 이 값을 출력하는 것인데, 결론적으로 잘못된 접근 방식이다.

 

위 생각이 이유를 찾는 과정에서 개인적으로 테스트 케이스가 더 많았다면 빨리 오류를 찾을 수 있었을 텐데 라는 생각을 했지만, 예시 입출력이 존재하는 것만으로 감사해야 하기에, 더욱 정진해야겠다는 마음을 먹었다..ㅠ

 

만약 [30, 34, 20, 16, 5] 라는 입력이 존재할 경우에 최초의 생각대로 풀면, 최소 값이 5이므로 최대 중량은 5 * 5 = 25라는 것이 된다.

 

여기서 문제 하단을 보면 모든 로프를 사용할 필요는 없으며, 일부를 선택하여 사용할 수 있다고 나와있다.

즉, 중량이 30인 로프 하나만 사용하더라도 반례가 되는 것이다.

 

그렇다면 어떻게 풀어야 할까?

 

이에 대한 나의 생각은 다음과 같다.

 

1. 우선 입력 값인 [30, 34, 20, 16, 5]를 정렬하여 [5, 16, 20, 30, 34]처럼 만든다.
2. 정렬된 입력 값들 중 최대 값부터 시작하여 최대 중량을 계산해보는 것이다.
3. 다음은 입력 값으로부터 발생 가능한 각 케이스별 최대 중량이다. 
   • [34] : 34
   • [34, 30] : 30 * 2 = 60
   • [34, 30, 20] : 20 * 3 = 60
   • [34, 30, 20, 16] = 16 * 4 = 64
   • [34, 30, 20, 16, 5] = 5 * 5 = 25
4. 따라서 입력 값을 기준으로 로프를 선택적으로 사용했을 때 구할 수 있는 최대 중량은 64가 되는 것이다.

 

이 방법을 사용하여 코드를 작성해보자.

 

---

 

코드

 

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

public class Main {
    public static void main(String[] arg) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        int[] ws = new int[count];

        for (int i=0 ; i<count ; i++)
            ws[i] = Integer.parseInt(br.readLine());

        Arrays.sort(ws);
        int max = ws[count-1];
        int mid = 0;
        for (int i=count-2 ; i>=0 ; i--) {
            mid = ws[i] * (count-i);
            if (mid > max)
                max=mid;
        }

        System.out.println(max);
        return;
    }
}

 

반복문에 사용된 인덱스 때문에 번잡하게 보일 수도 있지만, 일단 최대한 코드량을 줄여봤다.

 

코드를 보면,

 

1. count에 로프의 수를 저장한다.
2. int형 배열인 ws를 count만큼의 크기로 생성한다.
3. ws에 각 로프들의 정보를 저장한다.
4. Arrays.sort() 메서드를 사용하여 ws를 정렬한다.
5. 최대 중량이 저장될 변수인 max를 선언하고, 정렬된 ws에서 가장 큰 값인 ws[count-1]을 초기 값으로 저장한다.
   • count-1인 이유는 배열의 인덱스가 0부터 시작하기 때문이다.
6. for문에서 반복문 변수인 i를 count-2부터 0으로 설정하여 작성한다.
   • 정렬된 배열인 ws가 오름차순 정렬이기 때문에 큰 값부터 계산하기 위해 반복문 변수가 감소하는 반복문을 작성했다.
   • 변수 max에 초기 값인 ws[count-1]이 저장되었기 때문에 다음 순서부터 반복문을 시작하는 의미로 i의 시작이 count-2인 것이다.
   • 반복문을 돌리는 이유는 가장 큰 중량을 가진 로프부터 중량이 작아지는 순서대로 최대 중량을 계산하기 위함이다.
7. int형 변수 mid는 중간 결과 값을 의미하는데, mid에 ws[i] * (count-i)를 저장한다.
   • ws는 정렬되었기 때문에 각 회차에서 ws[i]의 의미는 배열 ws에서 가장 큰 값부터 작아지는 순서대로 고른 숫자들 중 가장 작은 중량을 가진 로프의 중량을 의미한다.
   • count-i의 의미는 각 케이스별로 사용된 로프의 갯수를 의미한다.
   • 즉 mid에는 로프들 중 중량이 가장 큰 값부터 작아지는 순서대로 로프들을 선택했을 때, 그들 중 중량이 가장 작은 로프의 중량에 사용된 로프의 수를 곱한 값이 저장되는 것이다.
8. max와 mid를 비교하여 max > mid라면 max에 mid를 저장한다.
9. 반복문이 종료된 후에 최종적으로 max에 저장된 값이 최대 중량이므로 이를 출력한다.

 

---

 

제출 결과

 

제출 결과

 

몇 번 안 되길래 ide에서 디버깅하고, 접근 방식을 바꿔서 다시 풀다가 겨우 맞은 느낌이다.. 더 열심히 해야지..