막대기

작성일 | In

[백준] 1094번 - 막대기

문제 링크

막대기를 반으로 쪼개가며 조건에 따라 일부를 버리면서 주어진 길이와 같도록 맞추는 문제이다.
자른 막대기 중 가장 짧은 길이의 막대를 찾기 위해 처음에 priority_queue를 사용했으나, 생각해보면 스택으로 간단히 해결할 수 있다.
스택에 처음 막대의 길이인 64를 넣어두고, 이후부터 막대기를 꺼내어 반으로 자른 뒤, 스택에 다시 넣으면 스택의 top에는 항상 가장 짧은 길이의 막대가 위치하게 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

stack<int> stick;
int len;
int X;

int main(void) {
    cin >> X;

    stick.push(64);
    len=64;
    while(1) {
        if(len == X) { cout << stick.size(); break; }

        int cur = stick.top();
        stick.pop();
        len-=cur;

        int div = cur/2;

        if(div == 0) continue;

        stick.push(div);
        int curlen = len + div;

        if(curlen < X) { 
            len = curlen + div; 
            stick.push(div); 
        } else if(curlen >= X) 
            len = curlen; 
    }
}
0%