백준 20055번 - 컨베이어 벨트 위의 로봇

2021. 1. 25. 23:04· Koala - 2기/B반

www.acmicpc.net/problem/20055

 

20055번: 컨베이어 벨트 위의 로봇

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부

www.acmicpc.net

 

2020 하반기 삼성 SW 역량테스트 문제 중 하나였어요.

 

생각보다 쉬웠다는 후기가 많아서 겁도 없이 미팅 때 라이브로 풀다가.. 

 

디버깅을 거의 30분 넘게 했는데도 잘못된 점을 찾지 못했어요ㅠㅠ..

 

그래서 너무 이상해서 질문 검색 게시판에 들어가보니 <문제에서 놓치기 쉬운 것들> 이란 글이 보이더라구요..

 

궁금하시면 한번 확인해보세요! 

 

저는 저 글을 보고 책상을 뿌실뻔 했어요!

 

제가 미팅 때 문제를 리뷰하면서 설명했던 부분이 완전히 잘못 이해했다는 것을 지금 알았기에 다시 적어보면

 

1. 1번째 칸에는 로봇을 올리고, N번째 칸에서는 로봇을 땅에 내린다.

 

이 뜻을 제가 완전히 잘못 이해했었는데, 저는 컨베이어 벨트가 위, 아래로 이어져 있어서 땅에 내린다는 게 컨베이어 벨트 아래쪽으로 내린다는 의미로 생각했었는데 지금 생각해보니 말도 안 되는 거였네요ㅠㅠ

 

어쨌든 이 조건을 통해 우리가 추리해내야 하는 것은

 

반드시 모든 로봇은 위쪽 컨베이어 벨트에서만 놀겠구나! 정도일 것 같네요.

 

2. 규칙에 따라 이동한다.

 

규칙은 문제에서 읽어보면 되고

 

중요한 점은 컨베이어 벨트 회전 -> 로봇 이동 -> 로봇 올리기 순서이므로

 

여기서 얻을 수 있는 것은

 

컨베이어 벨트 회전 시에는 내구도가 깎이지 않는다! 이 정도 일 것 같네요.

 

 

자 이제 실제 구현해 대해 생각해볼게요.

 

먼저 이어져있는 컨베이어 벨트를 구현해야 하는데

 

그림을 그려서 생각해보면 컨베이어 벨트의 이동은 배열 하나로 표현할 수 있어요!

 

ex) N -> N+1 즉 아래로 내려가는 것은 결국 다음 index로 이동하는 것과 마찬가지!

 

이때 주의할 점은 마지막 칸과 첫 번째 칸이 이어져 있다는 점!

 

그럼 보통 처음 생각하기에는

"아.. 귀찮네 이거 한 칸 이동시키려면 전부 오른쪽으로 한 칸씩 옮겨야 되자나"

"모든 배열의 원소를 움직이는 것도 귀찮은데 시간 복잡도가 괜찮을라나?"

 

다들 이런 생각 하셨을 거예요ㅎㅎ (저도 처음엔 그랬어요)

 

근데!

 

미팅 때 설명드렸듯이 C++ STL의 deque를 사용하면 O(1) 시간에 코드 두 줄로 이동이 가능하답니다!

 

#include <deque>

deque<int> belt;
// 벨트를 채워 넣었다고 가정해보면
belt.push_front(belt.back());
belt.pop_back();

belt란 deque가 1 2 3 4 5 6으로 채워져 있다고 가정해보면,

 

belt의 마지막인 6을 belt의 앞부분에 삽입하고, -> 6 1 2 3 4 5 6

 

belt에서 pop_back()을 하면 -> 6 1 2 3 4 5

 

짜잔! 

belt를 한 칸씩 회전시켰어요! 단 두줄만에!

 

이제 회전을 시켰으니 로봇을 이동시켜야 돼요.

 

저는 로봇의 위치를 담는 bool 형 배열 'check'를 선언했어요!

 

쉽게 말해서 check[index] = true 라면 index 번째 칸에는 로봇이 들어있다는 거에요.

 

로봇을 이동시키는 것도 아주 간단해요.

 

아까 위에서 구했듯이 로봇은 반드시 위에 컨베이어 벨트에만 존재할 수 있으므로

 

for (int i = n - 2; i >= 0; i--) { // 어차피 먼저 벨트에 올라갔으면 맨 앞쪽에 있겠지
	if (check[i] == true && dq[i + 1] >= 1 && check[i + 1] == false) {// i번째에 로봇이 있다면, i+1 번째 내구도가 남아있다면
		dq[i + 1]--; // i+1번째로 옮길 것임 -> 즉 내구도 깎임
		check[i] = false; // 갱신
		if (i == n - 2) continue; // i+1 == n-1, 로봇을 땅에 내려야 함
		check[i + 1] = true;
		}
	}

 

n번째(i=n-1이겠죠? 배열은 0부터 시작하니까) 칸에는 어떤 경우든 로봇이 있을 수 없어요!

 

그렇기 때문에 for (int i = n - 2; i >= 0; i--) 요 부분만 이동시켜주면 됩니다!

 

이동시킨다 = 내구도를 깎는다 이기 때문에

 

조건만 잘 신경 써준다면 어렵지 않게 구현할 수 있을 겁니다!

 

이렇게 로봇을 이동시켜주었다면 이제 로봇을 올려야겠죠?

 

로봇을 올리는 건 진짜 제일 쉬워요 진짜루

 

// 3. 로봇 올리기
// 로봇이 올라갈 수 있는 조건 : 0번 칸에 내구도가 1 이상, 로봇이 없어야 함
if (dq[0] >= 1 && check[0] == false) {
	check[0] = true;
	dq[0]--;
}

 

내구도가 남아있다면 올려주면 될 겁니다! 당연히 로봇의 위치도 갱신해주고요!

 

이제 정말 다했어요..

 

이제 종료 조건만 정리하면 되는데

 

종료 조건도 매우 간단해요. 내구도가 0인 칸이 몇 개인지만 알면 됩니다.

 

뭐.. 사실 시간 복잡도를 아낄 수 있는 여러 방법이 있지만

 

저는 굉장히 지쳤고 피곤하기 때문에 O(2N) 만에 구하는 브루트포스 방법으로 구현했어요.

 

// 컨베이어 벨트의 내구도 측정 -> 0이 몇 개 인지 반환
int find() {
	int ret = 0;
	for (int i = 0; i < dq.size(); i++) {
		if (dq[i] == 0) ret++;
	}
	return ret;
}

그냥 전부 돌면서 확인하는 코드입니다.

 

브루트포스 배웠으니까 다 알겠죠?

 

 

자! 이제 이 코드들을 싸악 다 합치면 끝이에요!

 

자세한 내용들은 코드에 주석으로 달아놓았으니 꼭 확인해보세요!

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

int n, k, x;
deque <bool> check; // 로봇이 있는지 없는지를 판단
deque <int> dq; // 내구도가 저장된 덱
int ans = 0;

// 컨베이어 벨트의 내구도 측정 -> 0이 몇 개 인지 반환
int find() {
	int ret = 0;
	for (int i = 0; i < dq.size(); i++) {
		if (dq[i] == 0) ret++;
	}
	return ret;
}

void simul() {
	while (1) {
		if (find() >= k) break;
		ans++;
		// 1. 벨트 회전
		dq.push_front(dq.back());
		dq.pop_back();
		// 벨트가 회전하면 위의 로봇들도 회전해야 함
		check.push_front(check.back());
		check.pop_back();
		if (check[n - 1] == true) check[n - 1] = false; // N번째 위치라면 로봇을 땅에 내림
		// 2. 가장 먼저 벨트에 올라간 로봇부터 회전하는 방향으로 한칸 이동
		// 로봇은 반드시 위 컨베이어 벨트에만 있을 것이다. (N 번째에 무조건 내리니까)
		for (int i = n - 2; i >= 0; i--) { // 어차피 먼저 벨트에 올라갔으면 맨 앞쪽에 있겠지
			if (check[i] == true && dq[i + 1] >= 1 && check[i + 1] == false) {// i번째에 로봇이 있다면, i+1 번째 내구도가 남아있다면
				dq[i + 1]--; // i+1번째로 옮길 것임 -> 즉 내구도 깎임
				check[i] = false; // 갱신
				if (i == n - 2) continue; // i+1 == n-1, 로봇을 땅에 내려야 함
				check[i + 1] = true;
			}
		}
		// 3. 로봇 올리기
		// 로봇이 올라갈 수 있는 조건 : 0번 칸에 내구도가 1 이상, 로봇이 없어야 함
		if (dq[0] >= 1 && check[0] == false) {
			check[0] = true;
			dq[0]--;
		}
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < 2 * n; i++) {
		cin >> x;
		dq.push_back(x);
		check.push_back(false);
	}
	simul();
	cout << ans << "\n";
}

 

코드를 잘 보면 주석을 빼고 나면 사실 몇 줄 안 되는 코드였어요ㅠㅠ

 

사실 여기까지 보면 그렇게 어려운 문제는 아니었던 것 같아요... (제가 할 말은 아니지만..)

 

혹시 저만 문제를 잘못 이해한 건가요.. 

 

어쨌든 이렇게 해서 해결해 보았고 생각보다 엄청 괜찮은 문제였네요!

 

다들 고생하셨고 목요일에 봐요~

 

 

 

 

 

'Koala - 2기 > B반' 카테고리의 다른 글

KOALA B반 - 1.28 미팅  (0) 2021.01.28
KOALA B반 - 1.25 미팅  (0) 2021.01.25
[1912번] 연속합  (0) 2021.01.23
[9461번] 파도반 수열  (0) 2021.01.22
[2668번] 줄어들지 않아  (0) 2021.01.22
'Koala - 2기/B반' 카테고리의 다른 글
  • KOALA B반 - 1.28 미팅
  • KOALA B반 - 1.25 미팅
  • [1912번] 연속합
  • [9461번] 파도반 수열
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1888)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (42)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (35)
    • Koala - 20기 (0)
      • 코딩테스트 기초 스터디 (0)
      • 코딩테스트 심화 스터디 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • dfs
  • C++
  • BOJ
  • 파이썬
  • 백트래킹
  • dp
  • 백준
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
백준 20055번 - 컨베이어 벨트 위의 로봇
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.