[BOJ] 백준 1817 - 짐 챙기는 숌 풀이

1. 문제

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

1817번: 짐 챙기는 숌

 

2. 풀이

백준 실버 5의 난이도인 문제이며, 배낭 문제와 유사하지만 배낭 문제보다 쉽게 접근할 수 있다.

입력으로 주어지는 N이 0이 아니라면 로직을 수행하고 0이라면 0을 출력한다. (17 ~ 18줄)
책의 무게를 리스트로 받은 후 하나씩 배낭에 넣어보면서 조건문을 수행하면 된다.

1. 탐색한 책의 무게가 M보다 클 경우 
- 이 경우 하나의 박스에 담을 수 없으므로 continue를 통해 반복문의 처음으로 돌아간다.

2. 현재 가방에 들어있는 무게(weight)에 탐색한 책의 무게를 더한 값이 M보다 작거나 같을 경우
- 이 경우 하나의 가방에 넣을 수 있으므로 탐색한 책의 무게를 weight에 더한다.

3. 현재 가방에 들어있는 무게(weight)에 탐색한 책의 무게를 더한 값이 M보다 클 경우
- 이 경우 새 가방을 추가해야하므로 가방의 개수(cnt)를 하나 더해준 후 현재 가방의 무게를 탐색한 책의 무게로 바꾼다.

마지막으로 cnt에 +1을 해준 값을 출력해주면 정답!!!
* cnt에 +1을 해주는 이유는 처음에 가방 값을 추가해주지 않고 반복문을 시작하기 때문

 

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Integer> list = new ArrayList<>();
        if (N == 0) {
            bw.write("0");
        } else {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                list.add(Integer.parseInt(st.nextToken()));
            }

            int cnt = 0;
            int weight = 0;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) > M) {
                    continue;
                }

                if (weight + list.get(i) <= M) {
                    weight += list.get(i);
                } else {
                    cnt += 1;
                    weight = list.get(i);
                }
            }
            bw.write(Integer.toString(cnt + 1));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}