2021 비버챌린지 그룹VI(고1~3) 문제 풀이

문제 1번_트루셰 타일

네 개씩 이어붙인 타일

타일을 네 개씩 붙여봤는데, C번 타일만 이음새가 맞지 않는 걸 확인할 수 있었습니다.

 

정답) C번

 

문제 2번_튜링 기계

1번과 2번은 표를 보고 판별하면 됩니다.

그리고 3번과 4번은 임의의 문자열을 만들어서 직접 시뮬레이션해보면 바로 풀리는 문제입니다.

 

[1번]

현재 문자가 1일 때 문자를 2로 바꾼다.

현재 문자가 1인 경우를 보면 다 _(공백)으로 바꾸기 때문에 틀린 선지

 

[2번]

현재 문자가 2인 경우에 문자를 1로 바꾼다.

현재 문자가 *(ALL)인 경우를 보면 *(ALL) 혹은 _(공백)으로 바꾸기 때문에 틀린 선지

 

[시뮬레이션]

임의의 문자열 S를 만든다.

S=00100

1. 00100, 현재 상태 0

2. 00100 -> 00100, 현재 상태 0

3. 00100 -> 00100, 현재 상태 0

4. 00100 -> 00000, 현재 상태 1

5. 00000 -> f 출력, 종료

 

[3번]

시뮬레이션 과정을 보면 3번 선지는 맞는 선지가 된다.

 

[4번]

시뮬레이션 과정을 보면 4번 선지는 틀린 선지가 된다.

 

정답) 3번

 

문제 3번_거미줄 퀼트

(1,3), (1,5), (1,6), (2,4), (2,7), (3,6), (4,6), (4,7)에 검은 천을 놓으면 된다.

 

정답, 각 좌표에 검은 천 놓기

 

문제 4번_간편한 표현

뒤에서부터 알맞게 잘라서 문자로 치환하면 됩니다.

 

맨 뒷 글자는 E

정답) TAKECARE

 

문제 5번_길찾기 로봇

이런 문제는 출발지에서부터 생각하는 것이 아닌, 도착지에서부터 생각하면 문제 풀이가 한결 수월해집니다.

각 도형별로 나눠서 생각을 해보겠습니다.

 

동그라미

빨간색으로 표시해놓은 부분을 보면 O가 우회전이여야만 도착지에 갈 수 있습니다.

 

엑스

마찬가지로 표시해놓은 부분을 보면 X는 직진이여야 도착지에 도착할 수 있습니다.

 

마름모

X가 직진, O가 우회전이라 할 때, ◇가 좌회전이여야만 도착지에 도달할 수 있습니다.

 

정답

 

문제 6번_위원회 구성하기

감사위원 한 명을 선택하고, 그다음 위원은 선택했던 위원들과 최대한 친분이 있는 사람을 선택합니다.

이런 방식을 반복하며 선택하다보면 감사위원회는 최대 3명으로 구성할 수 있다는 걸 알게 됩니다.

 

정답) 3명

 

 

문제 7번_통나무 정렬

통나무를 정렬 할 때, 통나무가 오름차순으로 정렬되어있는 상태가 하미드의 이동 횟수가 최소가 되는 경우일 겁니다.

그럴 때의 하미드의 이동 횟수는 통나무의 개수에서 1을 뺀 횟수입니다.

이를 일반화하면 하미드가 N개의 통나무를 정렬할 때는 최소 N-1번 이동해야 한다는 결론이 나오게 됩니다.

 

또한, 이동 횟수가 최대가 되는 경우는 내림차순으로 통나무가 정렬되어있는 경우일겁니다.

이럴 때는 하미드가 양쪽의 통나무를 한 번씩 바꾼 후에 다시 시작점으로 가게 됩니다.

이를 일반화하면 2*((N-2)+(N-3)+(N-4)....+1)+(N-1)이 된다는 걸 알 수 있습니다.

 

문제에서는 60개의 통나무를 크기순으로 정렬하라 했으니 최솟값은 59, 최댓값은 3481이 나오게 됩니다.

 

정답) 59번에서 3600번 사이

 

문제 8번_결함이 있는 전선 찾기

빨강 : 전기 공급, 파랑 : 단전

발전소에서부터 이어진 전선은 무조건 전기가 공급되어야 합니다.

그리고 불이 꺼진 집에는 연결된 모든 전선에 전기가 공급되지 않아야 합니다.

제일 오른쪽에 떨어진 집은 연결된 전선이 하나이므로 전기가 공급되어야 불이 켜질 수 있습니다.

 

초록 : 알 수 없음

그리고 아래쪽에 있는 두 집은 서로 연결되어야만 불이 켜질 수 있습니다.

남은 4개의 전선은 어디에 전기가 공급되어야만 불이 켜지게 되는지 알 수 없습니다.

 

정답

 

문제 9번_백설공주

처음 상태

4

42

425

4253

42536

정답) 42536

 

문제 10번_나뭇잎 가져가기

각 선지 별로 최선의 방법을 따라 시뮬레이션을 하다 보면 답이 나오게 됩니다.

 

[마일리가 A에서 2장의 나뭇잎을 가져가는 것으로 시작한다.]

저스틴이 B에 있는 나뭇잎을 모두 가져가게 된다.

 

[마일리가 B에서 2장의 나뭇잎을 가져가는 것으로 시작한다.]

저스틴이 A에서 나뭇잎 1개를 가져간다

-> 마일리가 A에서 나뭇잎 1개를 가져간다

-> 저스틴이 B에서 나뭇잎 1개를 가져간다

 

[저스틴이 A에서 나뭇잎 1장을 가져가는 것으로 시작한다.]

마일리가 B에서 나뭇잎 2장을 가져간다

-> 저스틴이 A에서 나뭇잎 1장을 가져간다

-> 마일리가 B에서 나뭇잎 1장을 가져간다

 

[저스틴이 Ⓑ에서 나뭇잎 1장을 가져가는 것으로 시작한다.]

마일리가 B에서 나뭇잎 2장을 가져간다

-> 저스틴이 A에서 나뭇잎 2장을 가져간다

 

정답) 저스틴이 A에서 나뭇잎 1장을 가져가는 것으로 시작한다.

 

문제 11번_저울질하기

식을 세워서 비교하면 쉽게 풀리는 문제입니다.

 

사진 1에서 D에 대해 정리를 하게 되면 D=A+B+C-20이 됩니다.

이를 사진 2에 대입하면 A+B=C+A+B+C-20이 됩니다.

식을 정리하면 2C-20=0 -> 2C=20, C=10이 됩니다.

 

이제 나와있는 선지에 참, 거짓을 부여하여 조건을 만들고 비교를 해보겠습니다.

 

1번 선지에서 C와 A가 같다면 B와 D도 같게 되고, 이는 2번 선지도 만족시키기 때문에 모순이 됩니다.

2번 선지 역시 모순이 생깁니다.

나머지 3, 4번도 경우의 수를 대입해보면 무조건 Ada가 Cezar보다 무겁기 때문에 답은 3번 선지가 됩니다.

 

정답 : 세자르가 에이다보다 가볍다.

 

문제 12번_아이스크림 기계

이 문제는 경우의 수가 8개이기 때문에 하나씩 대입해보며 풀었습니다.

ex) 1번 선지, A에 배치

이렇게 푸는 게 아닌 것 같긴 하지만 그래도 3분 이내에 풀 수 있습니다.

 

정답 : A와 B에 모두 배치한다.

 

문제 13번_무엇을 하는가

이 문제는 푸는 사람의 스타일에 따라 풀이 방법이 갈릴 것 같습니다.

 

1. 직접 코드를 짜서 푼다.

2. 손으로 푼다.

 

저는 2번으로 시도해봤다가 이게 답이 아닌 것 같다는 착각을 하는 바람에 1번으로 다시 한번 풀었습니다.

덕분에 시간 낭비를 꽤 많이 했습니다.

 

손으로 푸는 것은 문제에 나온 코드의 동작 과정을 따라가면 되니 별도의 해설은 하지 않겠습니다.

 

#include<cstdio>
#include<iostream>
using namespace std;

int f(int m){
	if(m<10){
		cout<<m;
	}
	else{
		f((m/10));
		cout<<(m%10);
	}
}

int main(){
	f(30241);
}

소스코드 실행 결과

정답 : 30241

 

문제 14번_비버 자리 배치하기

단순 정렬 문제지만 조건이 걸려있습니다.

"자리 재배치는 두 비버 간의 자리 교환을 통해서만 가능하다."

이 말은, 삽입 정렬과 같이 인덱스의 값이 뒤로 밀리는 정렬은 답이 아니라는 것입니다.

 

위 조건을 제외한 정렬에서 시간 복잡도가 적은 편인 선택 정렬 방법으로 비버를 움직이며 시뮬레이션해봤습니다.

 

2376145

1376245

1276345

1236745

1234765

1234567

 

정답 : 5번

 

문제 15번_보석 장식

문제에 나온 보석의 종류가 4가지 (동그라미, 별, 네모, 세모)이므로 각 보석 별로 동일한 보석이 가장 길게 이어질 수 있도록 만드는 경우를 따지면 됩니다.

 

동그라미

별

네모

세모

길이 6으로 세모가 가장 길게 이어진다는 걸 알 수 있습니다.

 

정답 : 6