정보올림피아드 2017 지역대회 고등부 오답노트

1. (1.1점) 12^2017 을 8진수로 표기할 때 가장 오른쪽에 나타나는 연속된 0의 개수는 몇 개일까?

 

12에 2가 몇 개?

12=(2^2)*3의 2017승이고 8은 2^3이다.

3은 아무리 곱해봤자 0이 나올 수가 없기 때문에 3 없다고 치고 2^2^2017 = 2^4034임

2^4034를 8로 바꿔보면 2*(8^1344)가 나오고 8에 n승에서 n이 0의 개수를 의미한다

 

2. (1.2점) 다음의 그래프에서 모든 간선의 길이가 1일 때 정점 p에서 정점 z까지 도달하는 가장 긴 경로의 길이는?

 

나가는 간선만 있는 노드를 지우고 도착지부터 거꾸로 올라가면 된다

 

3. (1.3점) 지구에서 달까지의 거리는 384,400km이다. 여러분에게 폭이 1cm이면서 길이가 충분히 길면서 두께는 0.1mm로 얇은 종이 띠가 주어졌다. 이 종이 띠를 반으로 접으면 접힌 부분의 두께가 두 배로 늘어난다. 최소 몇 번 이상을 접어야 접힌 부분의 두께가 지구에서 달까지의 거리만큼 두꺼워질 수 있을까?

 

384400km/0.1mm = 2의 몇 승?

단위 맞추기 문제

384400km = 38400 * 1000 m

=384400 * 1000 * 100 cm

=384400 * 1000 * 100 * 10 mm

 

직접 계산은 힘드니까 비슷한 수로 푼다

구하려는 수가 3 * 10^10 ~ 4 *　10^10 사이라서 오차는 신경쓰지 않아도 된다.

2^10 = 1024 = 1000

2^20 = 1000 000

2^30 = 1000 000 000

2^40 = 1000 000 000 000

2^41 = 2000 000 000 000

2^42 = 4000 000 000 000

384400 000 000은 2^42와 비슷하다고 할 수 있다.

그래서 42번

 

 

 

 

 

5. (1.5점) A, B, C 세 명이 계단 오르기를 한다. A는

한 걸음에 계단을 1칸 또는 3칸씩 오를 수 있고, B는

한 걸음에 계단을 1칸 또는 4칸씩 오를 수 있고, C는

한 걸음에 계단을 1칸 또는 5칸씩 오를 수 있다고 한

다. 세 명은 모두 가능한 최소의 걸음으로 계단을 오

른다. 공교롭게도 세 명 모두 같은 횟수의 걸음으로

계단의 가장 위에 도달했다고 한다. 이러한 계단의 최

대 칸 수는 얼마인가?

 

A가 C를 따라잡으려면 C가 최대한 1칸을 많이 걷게 해야 한다. 그래야 A나 B가 움직일 기회가 생기니까. 해보면 됨

 

6. (1.6점) 1번부터 10번까지 번호가 매겨진 10명의 학

생이 게임을 하기 위해 팀을 짜려고 한다. 팀은 1명

이상으로 구성되며 한 학생은 반드시 한 팀에만 속해

야 한다. 그리고, 어떤 학생 쌍은 사이가 좋아 무조건

같은 팀이 되어야 하고 어떤 학생 쌍은 사이가 좋지

않아 무조건 다른 팀이 되어야 한다. 이에 대한 정보

가 아래와 같을 때, 구성될 수 있는 팀의 최소 개수와

최대 개수는 각각 몇 개인가?

- 같은 팀을 원하는 학생 쌍: (1,7), (2,6), (4,5),

(6,9)

- 다른 팀을 원하는 학생 쌍: (1,9), (2,8), (4,8),

(5,6), (6,10), (7,8), (8,10)

그려보면 일단 최대 6개 그래프가 나옴

모을 수 있는 애들을 다 모으면 1 7 4 5 / 2 6 9 / 8 10 3 이렇게 3개

 

7. (1.7점) A, B, C, D, E가 처음 만나서 몇 명이 서로

악수를 했다. 이 때, 악수를 한 두 사람의 쌍(순서쌍

아님)들의 집합을 X라 하자. 적어도 한 쌍이 악수를

했고, 누구도 같은 사람과는 2번 이상 악수를 하지 않

았다면 X가 될 수 있는 집합은 모두 몇 개인가?

갈 수 있는 모든 간선 10개고 악수 하고 안 하고 두 경우 있으니까 2^10이고 아무도 안 할 수는 없어서 –1

2^10-1 = 1023

 

8. (1.8점) 철수와 영희는 구슬을 가지고 있다. 철수는

작은 구슬과 중간 구슬을 가지고 있고 영희는 큰 구슬

을 가지고 있다. 구슬의 가치는 작은 구슬 9개가 큰

구슬 5개와 같으며, 중간 구슬 9개가 큰 구슬 8개와

같다. 철수와 영희는 서로 같은 가치만큼 구슬을 바꾸

려고 한다. 구슬을 자를 수는 없으므로 철수는 작은

구슬 몇 개와 중간 구슬을 몇 개를 합쳐서 영희가 가

진 큰 구슬 몇 개와 바꾸어야 한다. 당연히 큰 구슬 1

개를 바꿀 수 있는 방법은 없다. 하지만 X개 이상의

큰 구슬에 대해서는 항상 바꿀 수 있는 방법이 있다.

 

작 = 5/9 큰 구슬 * A

중 = 8/9 큰 구슬 * B

 

작+중 해서 정수가 나오면 됨

(5a + 8b) / 9 가 정수가 나오는 경우를 생각해보면 되겠지만 보기를 보면서 빠르게 답을 찾자.

9가 없다고 치고 푼 다음에 나중에 나누고 올림할꺼임

 

2는 되는데 3은 안 됨.

23 24 25 26은 되는데 27은 안 됨

5개씩 돌기 때문에 연속된 5개를 만들 수 있으면 가능하다

28 29 30 31 32 가능이고 33부터는 반복이니까 28 이상부터는 전부 가능하다

 

28을 9로 나누면 3.x고 올리면 4

 

9. (1.9점) 9명의 남자는 각각 A개의 구슬을 자신의 주

머니에 갖고 있고, 3명의 여자는 각각 B개의 구슬을

자신의 주머니에 가지고 있다. 남자들이 모두 3명의

여자들에게 각각 C개의 구슬을 주고, 여자들도 모두 9

명의 남자들에게 각각 D개의 수의 구슬을 주어, 결국

남자와 여자 모두 같은 수의 구슬을 갖도록 하고 싶

다. 구슬의 교환은 동시에 이루어진다. 최종적으로 남

자와 여자가 가질 수 있는 같은 수의 구슬 개수의 최

솟값은 얼마인가? (단, A, B, C, D는 모두 1 이상의

자연수이고 서로 다르다.)

 

남) A – 3C + 3D

여) B – 9D + 9C

남과 여가 같음

 

C>D면 최소일 가능성이 적으니까 D>C라고 가정한다

D를 보면 남 A+3, 여 B-9

만약 A+3 = 4라면 C=2 고 D=3인데 남자가 –6개 줘야해서 불가능

그래서 A>=3C, B>=9D여야 한다

 

B-9D+9C = 9면

B=18, D=2, C=1이고

A-3C+3D 는

A=6 C=1 D=2 가 됨

 

답 9

 

 

10. (2.1점) 임의의 단순 무향 그래프 G=(V,E)의 라인 그래프(line graph) L(G)=(V’,E’) 는 아래와 같이 정의된다. V’=E 이며, E’={(e,e’)|e와 e’는 G에서 공통된 인접 정점을 갖는다. 아래 그림은 어떤 다섯 개의 그래프 G1,G2,G3,G4,G5의 라인그래프를 나타낸 것이다. 이 중에서 원래 그래프가 한붓그리기가 불가능한 것은 무엇일까?

 

라인 그래프는 연결되어 있는 선을 정점으로 하는 그래프다

 

왼쪽 그래프를 라인 그래프로 바꾸면 오른쪽처럼 된다 (아마..)

사실 잘 모르겠다. 틀릴 수도 있다. 그냥 선 사이에 정점이 있구나 참고만

 

이것저것 그려봐도 진짜 뭔지 모르겠다ㅋㅋㅋㅋ

대충 슥슥 그어봐도 느낌상 G2는 분명하게 한 붓 그리기가 안 된다고 생각할련다

참고-> http://wondangcom.com/217

 

 

11. (2.2점) 아래 식에 나타난 각 글자는 2이상 9이하의

서로 다른 한 자리 자연수이다. 아래 식이 성립한다고

할 때, R+T의 값은 얼마인가?

W R O N G

+ W R O N G

R I G H T

 

복면산은 노가다지만 노가다 범위를 좀 줄여보자

w는 올림이 되면 안되니까 2,3,4 중에 하나고, 그러면 r은 4,7,9 중에 하나임

5는 wrong에 들어가면 0이 되어서 1이나 right에 나와야 하는데

올림이라 r은 아니고 g/o는 짝수라(같은 수 두 개 더하면 짝수) 안 되니까 I/h만 가능

 

 

f(1) = f(-3)+f(5)

f(5) = f(1) +f(9)

f(9) = f(5) + f(13)

 

4개씩 움직임 2017로 나누면 나머지 1이라 답이 가능

n+4 = n이라고 생각하면

f(n) =f(n-4) - f(n-8)

1 5 9 13 17 21 25 29 ...

1 0 –1 –1 0 1 1 0

 

1 0 –1 –1 0 1 이 반복함

1 5 9 13 17을 4로 나누면

0 1 2 3 4 5니까 2017/4 = 504.X...1 이니까 1은 1이 되어야 하고 답은 1

 

15. 모순이 되는 부분을 찾아 바꿔줌

 

16. 숫자가 앞이면 안 됨

17.

.3은 4에서 반올림

 

19. 9글자+문자열은 항상 한글자가 더 있음

 

22.

1 3 5 7... 999 -> 500개

1000 * 500 / 2 = 25000

 

23.

((a^b+c)*c)%(d+d^e)

 

25.

swap(a,*c)부분 낚시

 

26.

배열이름 p는 보통 parent, d는 dest 자식을 의미함

int x[m] = {0,6,8,3,8};

int y[m] = {5,7,9,8,5};

 

(0, 5), (6,7)... 의 공통분모 구하기

 

28. 직접 해보기

 

29. 에라스토스의 체 문제

에라스토스의 체는 모든 소수를 구할 때 사용.

n이 소수인지 보려면 2~sqrt {n} (루트 n) 까지만 소수가 있는지 확인하면 된다

 

p배열: 소수가 아닌지 맞는지 확인

첫 이중for문에서 두 번째 for문 i*i로 해도 되고 그냥 i로 해도 상관 없음

 

t%10 -> 한자리씩 끊어 본다는 의미

if문: 1자리든 10자리든 4가 들어가면 0이고 아니면 증가

 

31. 그냥 해봄 (더 좋은 방법 있나? 모르겠다)

 

32.

0~9999까지 42 들어간거

42XX = 100

X42X = 100

XX42 = 100

4242 -> 이 경우 겹치니까 –1해줌

300-1 = 299

 

33.

int a[n]={0,1,2,0,2};

int b[n]={1,3,4,3,3};

s[0] 과 s[1] ... 스왑

 

0 1 2 3 4

1 0 2 3 4

1 3 2 0 4

1 3 4 0 2

0 3 4 1 2

0 3 1 4 2

0 1 2 3 4

0 3 1 4 2

 

2번째 -> 3번째 ->5번째 ->4번째 -> 2번째 반복 + 1은 자기 자신을 가리킴

4번하면 제자리니까 바꾸기 403번이고 2015번째는 0 2 4 1 3

2017이니까 2번 더 하면 2 0 4 1 3

2 1 4 0 3

 

1번

 

35.

n만큼 점프해서 언제 15를 벗어나나?

5만에 나가는 놈 구하는거 직접 해봐도 되고 거꾸로 세어 봐도 됨

 

36.

i-1 하고 &연산에는 규칙이 있음

i가 홀수면 1빼고

i가 짝수면 마지막 1을 0으로 바꾸고 0 뒤에 모든 0을 1로 바꿈

 

37. 원래 문자열에서 두 쌍을 세는 프로그램

 

40.

"):=%%=:(", -> 8

"\\(><)//", -> 7

"~[,_,]:3", -> 8

">_>^^<_<", -> 8

"o_O||O_o" -> 8

 

\\ 하나가 이스케이프 문자라 1글자임

 

41. 기억해두기

cnt[i--] 가 아니라 cnt[i]여야 함

 

42-43.

 

1. 시작 때는 무조건 사야 되고

2. 원래는 현재에서만 사야 되는데 문제를 바꿔서 다 돌아보고 제일 싼데서 사면 된다.

 

42.

1e18 -> 10^18이 이미 최소이므로 빼거나 더할 수 없다

① p = P[i]

② p += P[i - 1]

③ p -= P[i - 1]

④ p = P[i - 1]

⑤ p *= P[i - 1]

 

그러면 여기서 2 3 5번 걸러지고

1, 4 중에 앞에 보면 p[i-1]으로 비교하는데 뜬금없이 p[i] 대입하면 이상해서 4번 (야매)

 

43.

거리 * 가격 = 단가 라서 더할 일은 없음. 1, 2 제끼고

3, 4, 5 제일 싼 가격으로 사야하는 거니까 제일 적은 3번 (야매)

 

45.

어떤 상황이 있을 때

1. 내가 100 먹음

2. 내가 50 먹음 <- 이 상황을 선택해야 함. 항상 최선이기 때문에