[C++] 백준 20055번 : 컨베이어 벨트 위의 로봇

이 문제는 해석하기가 빡세다..ㅜ

 

아래의 글에서 문제를 잘 해석해주셨다

https://www.acmicpc.net/board/view/154341

참고하고 하나씩 풀면,,

엄청난 장고의 시간을 거쳐

풀었다......

넘넘.. (내기준)빡구현이었다....

1. 컨베이어 벨트 이동
2. 로봇 이동
3. 시작 위치에 로봇 추가

 

이 세 가지의 절차를 거쳐 풀면 된다.

 

1. 컨베이어 벨트 이동

벨트 이동은, start, endPos 두 개의 변수를 조정하며 상대적으로 이동한 것처럼 활용할 수 있도록 했다.

// 1. 컨베이어 벨트 이동
 start = (start - 1 + (2 * n)) % (2 * n); // n이 3이면 start는 0 -> 5
 int endPos = (start + n - 1) % (2 * n);  // 내리는 위치
 auto index = find(robots.begin(), robots.end(), endPos);

 

index는 벨트 마지막 부분 (내리는 위치)에 로봇이 있는 경우, 로봇을 삭제하기 위한 iterator를 기록한다.

 

2. 로봇 이동하기

다음은 로봇을 이동을 이동해야한다.

여기서 주의해야할 조건이 두 개가 있다. (조건이 많으수록 구현이 복잡하다. 꼼꼼하게 챙기기)

 

1. 내구도가 1 이상
2. 이동할 위치에 로봇이 없어야 함 (만약, 이동할 위치에 로봇이 있다면 움직이지 않는다.)

이 두 가지의 조건을 만족하는 경우에만 로봇을 이동시킬 수가 있다.

 // 2. 로봇이 이동한 칸의 값 -1
// it에는 현재 로봇의 위치좌표가 담겨있다.
for (auto it = robots.begin(); it != robots.end();)
{
    int nextLoc = (*it + 1) % (2 * n);

    // 로봇이 이동할 수 있는 경우 : 내구도 1 이상 && 로봇없음음
    bool noRobot = find(robots.begin(), robots.end(), nextLoc) == robots.end();
    if (a[nextLoc] && noRobot)
    {
        // 내구도가 0보다 크면, 1 감소시킨다.
        a[nextLoc]--;

        // 로봇 이동 자리 업데이트
        *it = nextLoc;

        // - zeroCnt 업데이트
        if (a[nextLoc] == 0)
            zeroCnt++;
        // 만약 로봇이 '내리는 위치'에 도달했다면,
        // 로봇을 리스트에서 제거하기
        if (nextLoc == endPos)
        {
            it = robots.erase(it);
        }
        else
        {
            it++;
        }
    }
    else
    {
        it++;
    }
    // 아니면, (내구도가 0이면) 내리는 위치인 경우에 내리기
}

 

코드에서 특이한 점(?) 은 iterator의 이동을 다루는 부분이다.

for문에서 다음 loop로 넘어갈 때, iterator를 변형해주어야 하는데,

로봇이 사라질 때 문제가 생긴다.

 

왜냐?

// 로봇을 리스트에서 제거하기
if (nextLoc == endPos)
{
    it = robots.erase(it);
}
else
{
    it++;
}

 

이처럼 erase함수를 쓰면, iterator에 해당하는 부분이 삭제되고 다음 요소를 가리키는 iterator를 반환한다.

따라서, for의 마지막 인자에 해당하는 부분에 무턱대고 it++를 해주면 중복으로 iterator값이 증가된다.

결국, 위에 처럼 조건문을 통해 iterator증가를 경우에 따라 다른 방식으로 증가되도록 개선해줘야한다.

 

3. start 위치에 로봇 두기

이제 로봇을 두고 턴을 마치면 된다.

여기에서도 두가지의 조건이 있다.

1. 해당 위치에 로봇이 없어야 한다.
2. 내구도가 1이상이어야 한다.

// 3. start위치에 로봇 두기 (0인 경우, 이미 로복이 있는 경우우 패스) - list에 추가하기
bool noRobot = find(robots.begin(), robots.end(), start) == robots.end();
if (a[start] && noRobot)
{
    robots.push_back(start);
    // 4. start 위체에 로봇을 둔 경우 칸의 값 -1
    a[start]--;

    // - zeroCnt 업데이트
    if (a[start] == 0)
        zeroCnt++;
}

 

이렇게 조건에 맞도록 코드를 구현해주면 한번의 턴이 최종적으로 끝나게 된다.

최종 : 반복문 탈출하기 및 풀이

while문을 탈출하는 건, 그냥 내구도가 0이 될 때마다 zeroCnt값을 추가하다가 그 값이 k이상이 되면 멈춘다.

그럼,, 끝이다

 

아래는 전체 코드다.

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(2 * n);
    for (int i = 0; i < a.size(); i++)
    {
        cin >> a[i];
    }

    int zeroCnt = 0, turn = 0;
    list<int> robots; // 로봇이 있는 자리의 index값을 저장한다.
    int start = 0;

    while (zeroCnt < k)
    {
        // 1. 컨베이어 벨트 이동
        start = (start - 1 + (2 * n)) % (2 * n); // n이 3이면 start는 0 -> 5
        int endPos = (start + n - 1) % (2 * n);  // 내리는 위치
        auto index = find(robots.begin(), robots.end(), endPos);

        // 1-1. 이동한 결과가 '내리는 위치'에 로봇이 있는 경우
        if (index != robots.end())
        {
            // 로봇 삭제
            robots.erase(index);
        }

        // 2. 로봇이 이동한 칸의 값 -1
        // it에는 현재 로봇의 위치좌표가 담겨있다.
        for (auto it = robots.begin(); it != robots.end();)
        {
            int nextLoc = (*it + 1) % (2 * n);

            // 로봇이 이동할 수 있는 경우 : 내구도 1 이상 && 로봇없음음
            bool noRobot = find(robots.begin(), robots.end(), nextLoc) == robots.end();
            if (a[nextLoc] && noRobot)
            {
                // 내구도가 0보다 크면, 1 감소시킨다.
                a[nextLoc]--;

                // 로봇 이동 자리 업데이트
                *it = nextLoc;

                // - zeroCnt 업데이트
                if (a[nextLoc] == 0)
                    zeroCnt++;
                // 만약 로봇이 '내리는 위치'에 도달했다면,
                // 로봇을 리스트에서 제거하기
                if (nextLoc == endPos)
                {
                    it = robots.erase(it);
                }
                else
                {
                    it++;
                }
            }
            else
            {
                it++;
            }
            // 아니면, (내구도가 0이면) 내리는 위치인 경우에 내리기
        }

        // 3. start위치에 로봇 두기 (0인 경우, 이미 로복이 있는 경우우 패스) - list에 추가하기
        bool noRobot = find(robots.begin(), robots.end(), start) == robots.end();
        if (a[start] && noRobot)
        {
            robots.push_back(start);
            // 4. start 위체에 로봇을 둔 경우 칸의 값 -1
            a[start]--;

            // - zeroCnt 업데이트
            if (a[start] == 0)
                zeroCnt++;
        }

        turn++;
    }

    cout << turn;
}

 

뭔가 조건들이 많아서 생각하는게 너무 귀찮았다..다른 좋은 방법이 있을 것만 같다.