백준 34126 (C++) 래환이의 초콜릿 포장 이야기

최초 업로드: 2025-10-23 11:25:26

최근 수정 시간: 2025-10-23 11:25:26

게시자: rlatjwls3333

카테고리: 백준

# [Silver III] 래환이의 초콜릿 포장 이야기

[문제 링크](https://www.acmicpc.net/problem/34126)

## 문제 설명

래환이는 창하를 위해 초콜릿을 포장하려고 한다. 그림 (a)와 같이 $1 \times 1$, $1 \times 2$, $1 \times 3$ 크기의 초콜릿이 각각 $A$, $B$, $C$개 있으며, 래환이는 그림 (b)와 같은 $N \times 2$ 모양의 주머니에 초콜릿 모두를 담고 싶어 한다. 단, 초콜릿은 중력의 영향을 받기 때문에 위에서부터 하나씩 넣어야 하며, 공중에 떠 있게 둘 수는 없다. 즉, 모든 초콜릿은 바닥 또는 이미 들어간 다른 초콜릿 위에 닿아 있어야 한다.

또한, 초콜릿은 (a)에 그려진 방향대로 넣거나 $90$도 회전해서만 넣을 수 있다. 따라서 넣을 수 있는 모든 초콜릿의 모양은 $1 \times 1$, $1 \times 2$, $2 \times 1$, $3 \times 1$ 중 하나이다. 그림 (c)는 주머니에 초콜릿을 담은 상태를 나타낸 것이다.

래환이는 주머니 밖으로 초콜릿이 넘어가지 않도록 하는 양의 정수 $N$의 최솟값을 구하고 싶다. 래환이는 얼마나 큰 주머니를 사용해야 할까?

## 입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다. $(1 \le T \le 5 \times 10^5)$

각 테스트 케이스의 첫 번째 줄에 세 개의 정수 $A$, $B$, $C$가 공백으로 구분되어 주어진다. 단, $A + B + C > 0$이다. $(0 \le A, B, C \le 10^8)$

## 출력

각 테스트 케이스마다 주머니의 높이를 나타내는 양의 정수 $N$의 최솟값을 출력한다.

## 풀이
c, b, a 순서대로 그리디하게 배치하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
        int a, b, c; cin >> a >> b >> c;
        int rem=c%2*3;
        if(rem && b) rem-=2, b--;
        while(rem && a) rem--, a--;

cout << (c+1)/2*3 + b + (a+1)/2 << '\n';
 }
}
```