[KOI 2019] 한국정보올림피아드 1차대회 중등부 풀이

10진수를 2진수로 표현할 수 있는지 파악하는 문제이다

2019 * 2021 = 4080399이다.

 

10진수를 2진수로 바꿀 때는 1이 될때까지 2로 나누면서 나머지를 오른쪽 끝에 쌓아주면 된다.

ex) 11

11/2 = 5...1

5/2 = 2...1

2/2 = 1...0

1

11은 이진수로 표현했을 때 1011이다.

 

4080399를 2진수로 표현하면

4080399/2 = 2040199...1

2040199/2 = 1020099...1

1020099/2 = 510049...1

510049/2 = 255024...1

255024/2 = 127512...0

...

 

따라서 오른쪽 끝 1의 개수는 4개이다

 

답) 4

 

3부터 15의 합은 18*6+9 = 117이다.

따라서 빠진 수는 11

 

답) 11

 

 

첫번째 자리는 16, 두번째 자리는 13이다.

10진수로 변환하기 위해서는 첫번째 자리에 20을 곱하고 두번째 자리에 1을 곱해서 더해주면 된다

16*20 + 13 = 333

 

답) 333

 

 

어른 한명이 강을 건너면 배가 건너편에 위치하게 된다.

배가 다시 돌아오기 위해서는 아이, 혹은 어른이 타고 돌아와야 되는데

어른이 타고 돌아오면 상황이 건너기 전과 똑같아지기 때문에 무조건 아이가 배를 다시 가지고 와야된다.

 

어른이 건너기 전에 아이 한명을 건너편에 두고오기 위해서

1. 아이 둘이 배를 타고 건너간다

2. 아이 하나만 배를 타고 돌아온다

 

이제 어른 한명이 건너고 아이가 돌아온다

3. 어른 한명이 배를 타고 건너간다

4. 1에서 건너간 아이 하나가 배를 타고 돌아온다.

 

총 네번의 이동으로 한명의 어른만 건너갈 수 있었다.

이러한 과정을 20명이 반복해야 되므로 총 20*4 = 80번 배가 움직여야된다

 

답) 80

 

 

400년 중에서 4의 배수인 윤년은 100번존재한다.

그리고 이 100번중에서 100의 배수인 해를 4번 더 셌으므로 4를 빼준다.

그리고 또 이 100의 배수인 해를 제외한 것 중에서 400의 배수는 제외하면 안되므로 1을 더해준다

따라서 400년중 총 윤년은 97번이다.

 

400년동안 365*400+97=146097일이 흘렀고

146097%7=0 이므로 시작한 요일 그대로 돌아온다.

 

답) 월요일

 

한붓그리기가 가능한 그림은 두가지 경우가 존재한다

1. 모든 꼭지점에서 모이는 모서리가 짝수일 때

2. 단 두개의 꼭지점에서 모이는 모서리의 수만 홀수일때, 나머지는 짝수

 

따라서 한붓그리기가 불가능한 종목은 맨 아래에 존재하는 두개의 그림이다.

그 중 두붓그리기를 직접해봤을 때 왼쪽 아래 그림이 가능하므로 정답이 된다

 

답) 5

 

장인 두명이 작업을 진행하는 것을 표를 통해 표현하면

7의 시간 만에 12까지 작업을 완료할 수 있다는 것을 알 수 있다.

시간	1	2	3	4	5	6	7	8
A	1	3	5	7	9	11	12
B	2	4	6	8	10

 

답) 7

 

7개의 원판을 한번에 두개씩 옮길수도 있으므로

1,2번 3,4번 5,6번 7번 이렇게 세트로 묶어서 이동한다고 하면

4개의 원판이 있는 하노이탑을 한번에 하나의 원판만 옮길 수 있도록 하는 것과 똑같다고 볼 수 있다.

 

하노이탑 원판을 옮기는 횟수는 점화식을 통해 구할 수 있다.

 

왼쪽 막대에서 n개의 원판을 오른쪽으로 옮기기 위해서는

1. 왼쪽 가장 밑 원판을 제외한 n-1개의 원판을 가운데로 옮겨가고

2. 왼쪽 가장 밑 원판을 오른쪽으로 옮기고

3. 가운데로 옮긴 n-1원판을 전부 오른쪽으로 옮긴다

 

$F_n$을 n개의 원반을 가진 하노이 탑을 왼쪽에서 오른쪽으로 옮기는데 필요한 횟수라고 한다면

$F_n = F_{n-1}*2 + 1$이 성립한다

 

$F_1 = 1$

$F_2 = 3$

$F_3 = 7$

$F_4 = 15$

 

답) 15

 

9글자 회문은 5글자까지만 구성하면 자동으로 완성된다

6번째부터 9번째까지는 앞에 선택된 알파벳에 의해 결정되기 때문이다

 

a,b,c를 통해 5글자를 구성할 때 200번째 오는 알파벳을 구하면 된다

전부 볼 필요 없이 경우의 수가 200번째를 넘지 않는 선에서 한번에 세면 빠르게 셀 수 있다.

a**** - 81
b**** - 81
ca*** - 27
cba** - 9
cbbaa - 1
cbbab - 1

81 + 81 + 27 + 9 + 1 + 1 = 200

따라서 200번째 회문은 cbbababbc이다

 

답) cbbababbc

 

매우 유명한 피보나치 문제이다.

점화식은 $F_n = F_{n-1} + F_{n-2}$

n = 1 - 1
n = 2 - 2
n = 3 - 3
n = 4 - 5
n = 5 - 8
n = 6 - 13
n = 7 - 21
n = 8 - 34
n = 9 - 55
n = 10 - 89

답) 89

 

 

이루어져야 되는 쌍은 전부 6가지이다

3-4, 3-5, 3-6, 4-5, 4-6, 5-6

여기서 4-6 쌍 때문에 성냥의 개수는 2의 배수가 되야된다

또한, 3-6 쌍으로 인해 성냥의 개수는 3의 배수가 된다.

따라서 6의 배수만 천천히 살펴보면 된다.

 

항상 5-6쌍을 가장 먼저 살펴보자 (수가 크고 서로소라서 상대적으로 이루어지기 힘듬)

6과 12는 당연히 이루어질 수 없다.

18도 이루어질 수 없다

24도 이루어질 수 없다

30도 이루어질 수 없다

36은 5*6+6으로 이루어질 수 있다

 

36은 3-4, 3-5, 3-6, 4-5, 4-6, 5-6 모든쌍에 대해 가능한것을 쉽게 계산해볼 수 있다.

 

답) 36

 

일단 이런 지저분한 문제를 봤을 경우 건너뛰고 뒤에 있는 문제들을 먼저 푸는 것을 추천한다

 

백만번째 자리를 채우는 숫자가 몇자리 수인지부터 구해보자.

 

1의자리 수를 전부 나열하면 총 9 * 1 = 9자리가 채워지고

10의자리 수를 전부 나열하면 총 90 * 2 = 180자리가 채워지고

100의 자리수를 전부 나열하면 총 900 * 3 = 2700자리가 채워지고

1000의 자리수를 전부 나열하면 총 9000 * 4 = 36000자리가 채워지고

10000의 자리수를 전부 나열하면 총 90000 * 5 = 250000자리가 채워진다

즉, 99999까지 나열했을 때 288889자리가 채워진다.

 

백만번째 자리까지 711111자리가 남았다.

100000번째 자리수가 118518개 있으면 711108자리를 채울 수 있다.

즉 100001부터 시작해서 118518번째인 218518까지 쓰면 백만번째 자리까지 세자리가 남는다.

이 세자리는 218519부터 시작하므로 백만번째 자리는 8....

 

인줄 알았는데 정답은 1이다.

이처럼 구하는데 오래걸리고 사소한 오류가 발생하기 쉬운 문제이므로 무조건 제치고 다른문제를 보자

 

아. 90000 * 5 = 250000에서 계산오류를 냈다. 다시 시작해서

10000의 자리수를 전부 나열하면 총 90000 * 5 = 450000자리가 채워진다

즉, 99999까지 나열했을 때 488889자리가 채워진다

 

백만번째 자리까지 511111자리가 남았다.

100000번째 자리수가 85185개 있으면 511110자리를 채울 수 있다. 

즉, 100001부터 시작해서 85185번째인 185185까지 쓰면 백만번째 자리까지 한자리가 남는다

이 한자리는 185186부터 시작하므로 정답은 1이다.

 

답) 1