-
[C][백준] 20055번 컨베이어 벨트 위의 로봇 풀이 : 원형 연결리스트, 삼성 SW 역량 테스트 기출 문제Algorithm/백준 2022. 11. 2. 23:12728x90
무려
삼성 SW 역량 테스트 기출 문제
이다. ㄷㄷ
상당히 문제가 난해하다.
난해하다는게, 문제의 조건을 오해하기 쉽다는 것이다.
사람들이 자주 햇갈리는 문제의 조건은 다음과 같다.
- 1단계는 과정 1, 2, 3, 4를 한꺼번에 묶은 것이다.
- 과정 1 → 2 → 3 → 4 → 1 → 2 → 3을 하고 끝나면 2단계에서 종료된 것이다!
- 처음에 로봇이 없어도 컨베이어 벨트는 돌아간다.
- N번째 칸에 가면 무조건 로봇을 내린다.
- 과정 2: 가장 먼저 벨트에 올라간 로봇부터 한 칸씩 이동한다.
- 이 조건을 간과하면 예제 입력 4번이 틀릴 것이다.
문제만 잘 이해하면 코드는 금방 짤 것이다.
그러나 문제를 이해하지 못하면 이런 사태가 날 것이다.
5트 만에 성공 이게 코딩 문제야? 논술 문제야?
백문이 불여일견 코드를 보고 이해해보자
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct _node { int life, index, robot; struct _node *next; struct _node *prev; } node; node *head; // 올리는 위치 (처음에는 1번 노드) node *tail; // 올리는 위치 바로 전 (처음에는 2N번 노드) node *out; // 내리는 위치 (처음에는 N번 노드) node *cur; // 현재 위치 int N, K, life_counter = 0; void push(int l, int idx) // 원형 연결 리스트 { node *newnode = (node *)malloc(sizeof(node)); newnode->life = l; newnode->index = idx; newnode->robot = 0; if (idx == N) out = newnode; if (head == NULL) { head = newnode; newnode->next = newnode; newnode->prev = newnode; } else { cur->next = newnode; newnode->prev = cur; newnode->next = head; } tail = newnode; head->prev = tail; cur = newnode; } int is_over() // 과정종료 { return life_counter >= K ? 1 : 0; } void turn() // 1. 한 칸 회전 & 로봇 내리기 { out->robot = 0; // out 비우기 head = head->prev; tail = tail->prev; out = out->prev; cur = head; out->robot = 0; // out 비우기 } void move() // 2. 로봇 옆으로 한 칸 이동 { out->robot = 0; // out 비우기 cur = out->prev; // 가장 먼저 벨트에 올라간 로봇부터 for (int i = 0; i < N - 2; i++) // head바로 앞까지 반복... out, head 제외한 나머지 { if (cur->robot == 1 && cur->next->robot == 0 && cur->next->life >= 1) // move 조건 { cur->robot = 0; cur->next->life -= 1; cur->next->robot = 1; if (cur->next->life == 0) life_counter++; } if (is_over()) // 과정종료 break; else cur = cur->prev; } } void place() // 3. 로봇 올리기 { cur = head; if (cur->life >= 1) { cur->robot = 1; cur->life -= 1; if (cur->life == 0) life_counter++; } } int main() { scanf("%d %d", &N, &K); for (int i = 1; i <= 2 * N; i++) // 2N만큼 원형 연결 리스트 생성 { int temp; scanf("%d", &temp); push(temp, i); } int stage = 0; cur = head; while (is_over() == 0) // 단계는 1, 2, 3, 4 과정을 하나로 묶은 것 { stage++; // cur = cur->prev; // 1. 한 칸 회전, 로봇 내리기 turn(); move(); // 2. 로봇 옆으로 한 칸 이동 if (is_over()) // 과정종료 break; place(); // 3. 로봇 올리기 } printf("%d", stage); return 0; }
728x90'Algorithm > 백준' 카테고리의 다른 글
[C][백준] 5567. 결혼식 구현하기 | 깊이 제한 그래프 탐색 (0) 2023.03.06 [C][백준] 1932. 정수 삼각형 구현하기 | Dynamic Programming (0) 2023.03.03 [C][백준] 1357번 뒤집힌 덧셈 풀이 : 문자열, 배열을 쓰지 않고, C 숫자 분리 (0) 2022.09.29 [C][백준] 2346번 풍선 터뜨리기 문제 풀이 : 원형 연결리스트를 사용하여 (0) 2022.09.07 [C][백준] 1158번 요세푸스 문제 : C, 원형연결리스트로 해결 (0) 2022.09.01 - 1단계는 과정 1, 2, 3, 4를 한꺼번에 묶은 것이다.