99클럽 코테 스터디 24일차 TIL [Greedy]

- 오늘의 학습 키워드 : Greedy

[문제 이름 : 저울 (백준, G2)]
문제 url : https://www.acmicpc.net/problem/2437

내가 작성한 코드는 아래와 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[num];

        for (int i = 0; i < num; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 추의 무게를 오름차순으로 정렬
        Arrays.sort(arr);

        // 측정 가능한 최소 무게
        int target = 1;

        for (int weight : arr) {
            // 현재 추의 무게가 target보다 크면, target이 측정할 수 없는 최소 무게
            if (weight > target) {
                break;
            }
            // target 범위 확장
            target += weight;
        }

        System.out.println(target);
    }
}

풀이 과정(풀이 시간 : 1시간)

처음에 조합으로 모든 경우의 수를 계산해서 무게를 구할 수 없는 최소 값을 접근하려고 헀지만, 메모리 초과가 떴다. 최소 무게니까 오름차순 정렬 후, 차근 차근 더해가며 풀이해도 문제가 없다는 것을 너무 늦게 깨달았다.

• target은 측정 가능한 최소 무게를 나타낸다. 무게 추의 최소 무게가 1이므로, 1로 초기화한다.
• 배열을 순회하며 현재 추의 무게 weight <= target 이라면 target 범위를 늘린다.
• weight > target이면 그 target이 측정 불가능한 최소 무게임을 의미한다.

 

내일은 금요일에 있을 코딩테스트를 위해 전반적인 개념을 다시 훑어볼 예정이다.