정보올림피아드 2015 지역대회 고등부 풀이

2015 시도예선 중고등부 문제

 

1.

8진법이라는 것은 1~10까지 곱한 수를 8로 계속 나누면서 나누어떨어지는 횟수를 의미한다. 물론 전부 계산할 필요는 없고 소인수분해해서 나누면 된다.

소인수분해하면 2^7*x가 나오니까 8=2^3 이 2번 나온다.

 

2.

두 정점을 연결하는 간선 1개를 추가하면 연결된 정점에 대한 차수는 A쪽과 B쪽에 2개가 증가한다. 즉 모든 정점의 차수의 합(연결된 다른 정점의 수의 합)은 항상 짝수임을 알 수 있고 차수의 합이 홀수인 경우를 찾으면 1번

 

3.

확통 문제. 1씩 넣어두고 네 정수를 합쳐서 6을 만든다. 4H6 = 84

다른 방법도 있는데 두 자리에 1씩 넣어두고 남은 두 자리 맨 앞+ 맨 끝수 = 8인 경우를 세보면

(1,7) (2,6) ... (4,6) ... (1,7) 이 있고 두 수를 곱하면 7+12+15+16+15+12+7 = 84

 

4.

5원과 8원을 사용해서 지불할 수 있는 금액을 표로 만들어서 세다보면 나온다.

지불 가능한 수가 연속으로 5번 나오면 그 다음 수부터는 5원만 더해도 전부 가능하기 때문에 연속으로 5개가 가능할 때까지 센다. 28부터 가능

 

5.

A*E에서 올림이 나오면 안 된다 -> A*E는 9보다 작거나 올림이 있을 경우 8보다 작다.

9보다 작으면서 D*E = A고 E*A = D (혹은 E*A+1 = D)인 경우를 해보면 D,E,A 순서대로 4,8,2 뿐이다. D=4

 

6.

한 수를 가운데 넣고 나머지를 두 개씩 짝지었을 때 여섯 쌍의 값이 같아야 한다.

만약 가운데 1을 넣었으면 나머지의 합은 90이고 6으로 나누면 15. 15는 1을 제외한 숫자들을 두 개씩 짝지을 수 있으니까 가능하다.

만약 6을 넣으면 91-6=85고 6으로 나눠떨어지지 않는다. 답은 6

 

숫자를 나열해서 풀 수도 있는데 1부터 13까지 써놓고 수를 하나 빼고 맨 앞+맨 뒤 수의 합이 계속해서 같은지 확인한다.

 

7.

마방진처럼 생겼다. 수를 모두 더한 값이 99이고 3줄씩 있으니까 3으로 나누면 각 줄을 더한 수는 33가 되어야 한다는 것을 알 수 있다.

 

8.

89에 제일 가까운 제곱수는 81이지만 제곱수로 7을 만들 수 없기 때문에 만들 수 있는 제곱수를 찾아 내려가다 보면 64+25를 찾을 수 있다.

 

참고로 이 방법은 BFS와 유사한데, 처음에 1개로 만들 수 있는 모든 값을 구하고 답이 없으면 그 값들로 2개를 사용해서 만들 수 있는 값을 만들고 또 없으면 3개, 4개 .. 확장하면 처음 찾는 값이 최소다.

 

9.

확통 문제다. 풀면 된다.

 

10.

오일러 경로 문제

한붓그리기가 가능한 경우는 [연결된 간선의개수가 홀수인 점을 홀수점, 짝수인 점을 짝수점이라고 했을 때 홀수점이 2개(오일러 사이클)거나 0개(오일러 경로)일 때]이다.

 

지금 그래프를 보면 차수가 홀수인 점이 6개 있어서 한붓그리기가 불가능하다. 홀수인 점 두 개를 연결하면 서로 차수가 1씩 늘어나서 짝수가 되고 한붓그리기 공식이 성립한다.

 

2개 선을 추가하면 홀수점은 2개만 남고 오일러 사이클을 만들 수 있다. 12+2=14

 

11.

주어진 숫자를 순서대로 정렬하고 작은 수부터 하나씩 더해가면서 만들 수 있는 수의 범위를 계산한다.

하다보면 1~30까지는 1~99까지 만들 수 있는데 그 다음 수가 104라서 100~103을 만들 수가 없다. 4개 수를 더 만들어야 하므로 4가 필요

 

12.

딱 보면 우박수 느낌이다.

한두개 계산하고 보기를 줄여나가면 된다.

1번을 해보면 3-10-5-16-8-4-2-1 이고 여기에 속하는 5와 8을 제외한다.

7을 해보면 7-22-11-34-17-52-26-13-40-20-10으로 10이 나오니까 끝내고 9는 9-28-14-7로 7이 나오므로 답은 9

 

13.

그래프를 압축해보자. 2*2칸으로 묶어보면 4*4가 나오고 그러면 ABCD도 왼쪽 맨 아래부터 ABC, B위에 C가 있는 모습이 된다.

() () () ()

() () () ()

() C () ()

A B C ()

또 압축을 하면

() ()

ABC D

이런 2*2 사각형이 되고

그러면 문제도 각 영역을 비워두고 모든 타일을 채울 수 있나? 로 바뀌게 된다.

이 때 ABCD 모두 그 칸을 제외한 모든 곳을 ㄴ모양으로 채울 수 있기 때문에 불가능한 곳은 없다.

 

근데 사실 이 문제는 가로 세로의 크기가 2^k라면 모든 칸을 채울 수 있다고 한다.

 

14.

직접 세보며 풀었다.

더 쉬운 방법으로는 150을 10로 나누면 각자 15개가 있어야 15개를 가지려면 어떻게 해야 하는지 적는다.

 

남은 사람 :　 10 13 26 11 15 12 18 13 25 7

15와 차이 :　 -5 -2 11 –4 0 –3 3 -2 10 -8

 

이 때 26개 가진 사람이 10, 13, 11개 가진 사람에게 나눠준다. 3번

-3과 3은 서로 준다. 1번

10개 가진 사람이 양쪽으로 준다. 2번

총 6번

 

15.

이 문제는 처음 봤을 때는 똑같은 형태를 예전에 퍼즐책에서 본 기억이 나서 쉽게 풀었던 기억이 나는데 지금 보니까 너무 오래됐는지 기억이 가물가물하다. 그래서 그냥 2진수로 풀었다.

 

와인이 1000개기 때문에 쥐는 적어도 10마리가 있어야 한다. 2^10 = 1024

쥐에 번호를 붙이고 이진수로 표현한다.

 

a b c d e f g h i j

병1 0 0 0 0 0 0 0 0 0 1 = 1

병2 0 0 0 0 0 0 0 0 1 0 = 2

병3 0 0 0 0 0 0 0 0 1 1 = 3

병4 0 0 0 0 0 0 0 1 0 0 = 4

...

병1000 1 1 1 1 1 0 1 0 0 0 = 1000

 

그리고 모든 쥐가 세로로 내려오면서 마신다. 내려오다가 1을 만났다면 쥐는 죽는다.

죽은 쥐는 1로 안 죽은 쥐는 0으로 표시하면 이진수가 나오고, 그 이진수에 독이 들었다고 알 수 있다.

이 때 쥐가 죽는 최대 독든 와인 개수는 9개인데, 10개가 되면 1000을 넘기 때문이다.

그래서 세보면 1이 9번 들어가는 이진수는 511, 767, 895, 959, 991, 다섯 개가 나오며 이 다섯 개를 빼고 다시 숫자를 붙여보면 1~1005까지 나온다. 따라서 10마리 쥐를 사용하고 최대 8마리까지 희생시키면 독이 든 와인 병을 찾을 수 있다.