백준 20055 (삼성 SW 역량평가 기출) - 컨베이어 벨트 위의 로봇

 이 포스팅은 삼성 GIST 모터 트랙 대비 과정에서 풀었던 기출 문제에 대한 글입니다. 모두 백준에 공개된 문제들만 있으며, SW Expert Academy에서만 다루는 문제들은 저작권 문제로 업로드 되지 않습니다.

---

1. 문제 내용

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

문제 난이도: GOLD V

2. 접근법

• ‘컨베이어 벨트’가 등장하는 순간 덱을 바로 떠올릴 것.
• 그 이후부터는 문제를 한 문장 씩 읽어보면서 차근차근 구현하면 됨.

3. 풀이 코드

#include <iostream>
#include <deque>

using namespace std;

int N, K;
deque<int> dq1; // 위 내구도
deque<int> dq2; // 아래 내구도
deque<bool> robots; // 로봇 존재 여부

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    //input
    cin >> N >> K;
    for(int i = 0; i < N; i++) {
        int tmp; cin >> tmp;
        dq1.push_back(tmp);
    }
    for(int i = 0; i < N; i++) {
        int tmp; cin >> tmp;
        dq2.push_back(tmp);
    }
    for(int i = 0; i < N; i++) { // 초기화
        robots.push_back(false);
    }
    
    //simulate
    int cnt = 0;
    //cout << "start" << '\n';
    while(K > 0) {
        
        //1. 벨트 및 로봇 회전
        
        //1-1 벨트 덱 회전
        int tmp = dq1.back(); dq1.pop_back();
        dq2.push_front(tmp); tmp = dq2.back(); dq2.pop_back();
        dq1.push_front(tmp);
        //cout << cnt << " belt rotated\n";
        
        //1-2 로봇 덱 회전
        robots.pop_back(); 
        if(robots.back()==true) robots.back() = false; // 로봇 내리기
        robots.push_front(false);
        //cout << cnt << " robots rotated\n";
        
        //2. 이동 가능 시 이동(뒤부터 순서대로) & 내구도 갱신
        for(int i = N - 2; i >= 0; i--) { //맨 끝은 항상 없으므로 N-2부터 해도 됨
            if(robots[i] && !robots[i+1] && dq1[i+1] > 0) {
                robots[i] = false; robots[i+1] = true; //로봇 이동
                dq1[i+1]--; if(dq1[i+1] == 0) K--; //내구도 갱신 + 갱신될 때마다 0인지 확인
                if(i+1 == N-1) robots[i+1] = false; //끝에 도착했으면 내리기
            }
        }
        
        //3. 로봇 올림
        if(!robots[0] && dq1[0] > 0) {
            robots[0] = true; //로봇 올리기
            dq1[0]--; if(dq1[0] == 0) K--; //내구도 갱신 + 갱신될 때마다 0인지 확인
        }
        
        cnt++;
    }
    
    cout << cnt;
    return 0;
}

4. 중요 포인트

• 리스트 + 회전 –> 바로 덱 떠올리기!
• 이런 식의 빡구현 문제는 머릿속에서 시뮬레이션 해보면서 한 단계씩 해보는 게 좋은 것 같음.
• 디버깅 용으로 출력문 찍을 때는 sync 끄고 하기.
• 입력 안받는 자료구조는 초기화하는 거 까먹지 말기!