백준 20055번 C++

 

 

이번에도 삼성 기출문제이다.

문제에서 요구하는 그대로 구현하면 되는 문제!

 

 

내가 생각한 이 문제의 핵심은

 

1. deque와 pair를 이용하는 것

2. 가장 먼저 놓인 로봇은 항상 가장 멀리 가 있다는 것 (한칸씩 이동하므로 당연)

 

두 가지만 생각하면 문제를 풀 수 있다.

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>


using namespace std;

int main() {
        
    int N, K;
    int phase = 0, limit = 0, temp;
    deque<pair<int, bool>> container;
    
    cin >> N >> K;
    
    for(int i = 1; i <= 2 * N; i++) {
        cin >> temp;
        container.push_back({temp, false});
    }
    
    
    while(limit < K) {
        
        phase++;
        
        // 1. 회전
        container.push_front(container.back());
        container.pop_back();
        if(container[N - 1].second) container[N - 1].second = false;
        
        
        for(int i = 2 * N - 1; i >= 0; i--) {
            
            // 다음 위치
            int next = (i + 1) % (2 * N);

            // 로봇이 있고, 다음으로 갈 수 있다면
            if(container[i].second && !container[next].second && container[next].first > 0) {
                container[i].second = false;
                
                if(next != N - 1) container[next].second = true;
                if(--container[next].first == 0) limit++;
            }
            
        }
        
        if(container.front().first > 0) {
            container.front().second = true;
            if(--container.front().first == 0) limit++;
        }
    }
    
    cout << phase << "\n";
}