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

1. 계산

 

2.

원래는 1~9가 몇 번 나오는지를 셌는데 그렇게 세니까 복잡하다.

그냥 1이 몇 개 2가 몇 개 이런 식으로 세는 게 좋다.

나올 수 있는 자리는

?

_?

?_

?__

 

이렇게 네 가지이고

1은 한 자리에 1개 두 자리에 10개 + 9개 나오고 3번째 자리 1개 가능하니까 21개

2는 1개 / 19개 만 가능하니까 20개

3도 20개

... 해서 1만 빼고 20개씩 나온다

(1~9)*20 + 1 = 901

 

3.

철수 110 바퀴 = 3300

30, 25, 40의 최소 공배수 = 600

3300 보다 작은 600의 배수를 찾아 세면 됨

5개

 

4.

이진탐색, 나눠보면 10번

 

5.

해보면 나옴

1 –2 –3 –1 2 3 이 반복된다

 

6.

그냥 확통 문제

 

1, 2 최소 18

2, 3 최소 11

1, 3 최소 13 이니까

 

1+2+3-1/2최소-1/3최소-2/3최소 = 24

30-24 = 6

 

7.

갑-병-정 이랑 병-을-갑 만 가능한데 전자는 정을 맞춘 사람이 둘이라 안 됨

 

8.

일단 1이 들어가는 게 몇 개?

1 = 1

1_ = 10

1__ = 100

111개

 

2,3도 같으니까 333개고

4 = 1

40 = 1

40_ = 10

41

410

411

412

413 = 350번째

 

9.

최악의 경우 생각

3번 필요

 

10.

세제곱 했을 때 1자리에 7나오는 수는 3

???? = 10a + 3

(10a+3)^3 = ...+270a +　27 -> 끝자리가 7이어야 하니까 a는 5고 ??53이니까

가능한건 1953

 

12.

11번에서 계산한 것을 보고 규칙찾기

f(n) = f(n-2)+f(n-1) + 1

 

17.

윤년 계산

 

19.

sun += a%3;

a /= 3;

3진법 변환 문제

 

25.

약수의 개수가 홀수일 때 cnt 증가

약수가 홀수면 완전 제곱수

루트2013 = 44.X라서 44

 

27.

직접 세면서 아 이건 직접 세는 문제가 아닌 거 같은데 했는데 진짜 세면 바보

백트래킹 + DP 문제였다.

표로 만들어 본다. if문에 걸리지 않는 수는 서북 + 북 + 동북 더한 값이다

 

0 1 2 3 4 5 6

0 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

2 1 3 1 1 1 1 1

3 1 5 5 1 1 1 1

4 1 11 11 7 1 1 1

5 1 23 29 19 9 1 1

6 1 53 71 57 ...

 

f(6,3) = 57

 

29.

달팽이 배열

 

33.

플러드 필 문제

덩어리를 센다.

 

34.

파스칼의 삼각형

nCr = n-1Cr + n-1Cr-1 공식을 그대로 가져온 것

 

36.

자기 자신을 제외한 약수의 합이 서로를 나타내는 수 = 친화수

친화수를 찾는 문제였다

220 284

 

37.

b에 조건이 둘 다 0이어야 한다는 말은

뒷 비트가 00이라는 의미고 4의 배수가 되어야 한다.

 

39.

if문은 왼쪽 그룹 정보 복사하고 오른쪽으로 넘어간다는 의미