[백준] 컨베이어벨트 위의 로봇 20055번 (c++)

출처 : https://www.acmicpc.net/problem/20055

 

풀이 방법

 

단순 시뮬레이션 문제이다.

배열의 범위만 잘 고려하면 풀이할 수 있다. (중간에 -1을 하는 과정에서 다시 시작 위치로 초기화하기, 음수가 안되게 +2n을 한 후 % 2n연산하기)

문제에 한 칸에 로봇이 2개 이상 올라갈 수 없다는 조건이 없어 애매했지만, 한 칸에는 로봇이 1개만 올라갈 수 있다.

 

핵심 아이디어

 

1. 벨트 회전(rotate)

• 실제로 배열을 돌리는 대신, “시작 인덱스(startIndex)”를 조정하는 방법을 쓴다.

• 예: startIndex를 1 감소(startIndex = (startIndex - 1 + 2N) % (2N))시키면, 컨베이어 벨트가 시계 방향으로 한 칸 돌아간 것과 같은 효과를 낼 수 있다.

• 올리는 위치는 항상 startIndex가 가리키는 인덱스이다.

• 내리는 위치는 (startIndex + N - 1) % (2N)로

• 벨트가 회전하면서 내리는 위치 위에 있던 로봇은 즉시 제거해야 한다. (로봇이 내리는 위치에 도달하면 내린다고 문제에서 명시)

 

2. 로봇 이동(robot move)

• 벨트 회전이 끝난 뒤, 내리는 위치 바로 앞 칸에 있는 로봇부터 역순으로 확인하며 이동 가능 여부를 본다.

• 이동 조건:

1. 다음 칸(로봇 진행 방향)에 로봇이 없다.

2. 다음 칸의 내구도가 1 이상이다.

• 이동하면 다음 칸의 내구도는 1 감소한다.

• 이동 후 내리는 위치에 도착한 로봇은 즉시 제거한다.

 

3. 로봇 올리기(put robot)

• 로봇을 올리는 위치(startIndex)의 칸 내구도가 1 이상이고, 그 자리에 로봇이 없다면 로봇을 올린다.

• 올릴 때 해당 칸의 내구도를 1 감소시킨다.

 

4. 내구도 0 확인

• 매 단계가 끝날 때마다 내구도가 0이 된 칸의 개수를 확인하고, 이것이  K  이상이면 과정을 종료한다.

 

#include <iostream>

using namespace std;

int n, k;

// 내구성이 k개 이상인 경우 위 과정을 종료한다.
int belt[201];
int Ai[201];
int robot[201];

int main() {
    cin >> n >> k;
    for (int i = 0;i < 2 * n;i++) {
        cin >> Ai[i];
    }
    int step = 0, start_idx = 0;    
    while(true) {         
        step++;
        // 한 칸 회전
        start_idx--;
        if (start_idx == -1) start_idx = 2*n-1;
        // 내리는 로봇 제거
        robot[(start_idx + n - 1) % (2 * n)] = 0;
        //로봇 이동하기
        int now_idx = (start_idx + n - 2) % (2 * n);
        int next_idx = (now_idx+1) % (2 * n);
        while(true) {            
            if (robot[now_idx] == 1 && robot[next_idx] == 0 && Ai[next_idx] != 0) {
                robot[next_idx]++; // 로봇위치 이동
                robot[now_idx]--;
                Ai[next_idx]--; //내구성 줄이기
                if (next_idx == (start_idx + n - 1) % (2 * n)) robot[next_idx] = 0; // 로봇이 이동 후 내리는 위치이면 내리기
            }
            if (now_idx-1 == -1) now_idx = 2 * n;
            if (next_idx-1 == -1) next_idx = 2 * n;
            now_idx--, next_idx--;
            // 위 벨트의 로봇 이동 완료
            if (now_idx == (start_idx - 1 + (2 * n)) % (2 * n) ) break;            
        }

        //올리는 위치 로봇 올리기
        if (Ai[start_idx] != 0) {
            robot[start_idx]++;
            Ai[start_idx]--;
        }
        // 내구도 0인거 검색
        int cnt = 0;
        for (int i = 0;i < (2 * n);i++) {
            if (Ai[i] == 0) cnt++;
        }
        if (cnt >= k) break;
    }
    cout << step;
    return 0;
}