백준 1434번 [책 정리](C++) -yes6686- 티스토리

백준 문제 풀이: 1434 [책 정리]

---

문제 링크: https://www.acmicpc.net/problem/1434

문제 설명:

책장 n개의 각 칸의 용량과 책 m개의 크기가 주어졌을 때, 책들을 책장에 순서대로 넣습니다. 책을 넣고 남는 책장 공간의 크기를 구하는 문제입니다.

---

문제 해결 코드

// 백준 1434 - 책 정리
#include <iostream>
using namespace std;

int shelf[1001]; // 책장 용량
int books[1001]; // 책 크기

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m; // 책장의 칸 수와 책의 수

    int remainingSpace = 0; // 남는 책장 공간
    for (int i = 0; i < n; i++) {
        cin >> shelf[i]; // 책장 용량 입력
        remainingSpace += shelf[i]; // 책장의 총 용량
    }

    for (int i = 0; i < m; i++) {
        cin >> books[i]; // 책 크기 입력
    }

    int j = 0; // 현재 책장 인덱스
    for (int i = 0; i < m; i++) {
        while (j < n) {
            if (shelf[j] >= books[i]) { // 책이 현재 책장에 들어갈 수 있으면
                shelf[j] -= books[i]; // 책장 용량 감소
                remainingSpace -= books[i]; // 남는 공간 감소
                break;
            } else {
                j++; // 다음 책장으로 이동
            }
        }
    }

    cout << remainingSpace << '\n'; // 최종 남는 공간 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 책을 순서대로 책장에 넣으며, 책장의 현재 용량과 책의 크기를 비교합니다.
  • 책이 들어갈 수 없는 경우, 다음 책장으로 이동합니다.
• 구현 세부사항:
  • 책장이 충분하지 않아 책을 모두 넣을 수 없는 경우, 남은 공간은 책이 차지하지 않은 책장의 용량입니다.
  • 책장 용량과 책 크기는 각각의 배열로 관리하며, 반복문으로 순차적으로 처리합니다.
• 시간 복잡도 분석:
  • 최악의 경우, 모든 책이 모든 책장을 순회하므로 O(n ⋅ m)입니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!