2010 시도예선 중고등부 문제

수학문제

1. 1부터 2000까지 정수 중에서 4의 배수 또는 6의배수는

500+333-166 = 667

위의 정수들 중에서 5의 배수인 것은 20 또는 30의 배수이므로

100+66-33 = 133

둘을 빼면 534 따라서 정답은 3번

2. 직접 해보는 수 밖에 없다. 최대는 13, 최소는 11 따라서 24

3. n개의 항을 가지는 수열로 나누면 항의 개수가 1, 2, 3, 4 이므로

200에 가장 근접할 때는 190에서 19의 수열이 끝날 때이다.

20의 수열은 1부터 해서 10에서 걸린다.

따라서 200번째는 10이다.

4. 한명씩 참이라고 가정하고 나머지를 점검해서 모순이 생기면 정답이 아닌거다. 따라서 다 해보면 D가 나온다.

5. ABCDE 사전순 나열 문제를 풀때는 

첫 번째 단어가 몇 번을 주기로 바뀌는지 -> 64번

두 번째 단어가 몇 번을 주기로 바뀌는지 -> 15번

세 번째 단어가 몇 번을 주기로 바뀌는지 -> 4번

네 번째 단어가 몇 번을 주기로 바뀌는지 -> 1번

를 중점적으로 보면된다.

따라서 계산해보면 첫 번째 단어가 A에서 C가 될때까지는 (64 + 1) * 2 +1번

(1을 더하는 이유는 AA부터 주기에 들어가므로 A까지 세주기 위함)

두번째 단어가 A에서 D가 되기까지는 (15 + 1) * 2 + 1번

세번재 단어가 A가 되기까지는 1번

네번째 단어가 B가 되기까지는 1번

따라서 총 166번

6. 작은 수부터 앞에 넣어주는 방식으로 구하면 

5를 맨앞으로 오게 하기 위해서 4번

10을 맨앞으로 오게하기 위해서 2번

15를 맨앞으로 오게하기 위해서 1번

20을 맨앞으로 오게하기 위해서 2번

25를 맨앞으로 오게하기 위해서 1번

총 10번이다.

7. 중 3때 배운 벤다이어그램을 그리면 쉽게 풀린다. 23명

8. 일단 가능한 모든 경우의 수는 6!이다. 

그러나 한가지 형태가 한 면을 중심으로 4번 돌 수 있기 때문에 중복이 4개 생긴다.

그리고 한면을 중심으로 볼 때 그 한면이 다른 면에 있을 때 중복이 6개 생긴다.

따라서 6! 나누기 4 나누기 6으로 30이 나온다.

9.  전형적인 DP문제이다. 

N-1에서 N으로 갈때 2*1을 넣는 경우의 수가 한가지 있고

N-2에서 N으로 갈때 2*1을 세로로 두개 넣는 경우와 2*2를 넣는 경우가 있으므로 (2 * 1 세로 두개는 위에 포함되므로 제외한다.)

점화식은 다음고 같이 된다. A(N) = A(N-1) + 2 * A(N-2)

점화식을 따라가면 A(6)은 43이 나온다.

10. 크기순서대로 세면 된다.

먼저 직각으로 바로 보이는거 먼저

크기 1은 16개

크기 4는 9개

크기 9는 4개

크기 16은 1개

이제 비스듬한거를 보자

크기 2는 9개

크기 4는 8개

크기 6은 3개

다 더하면 50개

11. 식으로 세워서 풀면 편하다.

A + B + C + D = 1000

A = 2 * C

B = D + 100

C = B + 200

D = 제곱수

여기서 돈이 0원인 사람이 거짓말을 하고 있다.  하나씩 해보면

B가 0일 때 C는 200원 A는 400원 D는 400원으로 성립한다. 따라서 A+D는 800

12. 오른쪽에서부터 하나씩 보면 된다. J는 뒤에 0명이 자신보다 키가 작으므로

J

I는 뒤에 1명이 자신보다 키가 작으므로

J I

H는 뒤에 1명이 자신보다 키가 작으므로

J H I

G는 뒤에 3명이 자신보다 키가 작으므로

J H I G

이런 식으로 뒤에서 부터 한명 씩 나열하면 

뒤에 사람들중 자신보다 작은 사람이 N명 있으면

나열된 알파벳에 N번째에 끼워넣으면 된다. 그러면 전체적으로 키순으로 정렬된다.

C J H F A E B I G D순으로 정렬된다.

따라서 E보다 큰사람은 4명

13. 그냥 구하면된다. 8*6 + 4*6 = 72

14. 한붙그리기처럼 생각하면 된다. 한붙그리기는 각 노드가 간선의 개수가 모두 짝수일 때 시작한 곳으로 다시 돌아올 수 있다.

따라서 홀수인 노드 4개를 두개씩 짝지을 때 그 비용이 최소가 되도록 하면 된다.

해보면 답은 76

15. 

노드가 5개일 경우 최상위 노드를 중심으로 나뉘는 경우는 (0, 4) (1, 3) (2, 2) (3, 1) (4, 0)

노드가 4개일 경우 최상위 노드를 중심으로 나뉘는 경우는 (0, 3) (1, 2) (2, 1) (3, 0)

노드가 3개일 경우 최상위 노드를 중심으로 나뉘는 경우는 (0, 2) (1, 1) (2, 0)

노드가 2개일 경우 최상위 노드를 중심으로 나뉘는 경우는 (0, 1) (1, 0)

노드가 1개일 경우의 경우의 수는 1

다시 올라가면

노드가 2개일 경우 1 + 1 = 2

노드가 3개일 경우 2 + 1 * 1 + 2 = 5

노드가 4개일 경우 5 + 1 * 2 + 2 * 1 + 5 = 14

노드가 5개일 경우 14 + 1 * 5 + 2 * 2 + 5 * 1 + 14 = 42

총 42개

코딩문제

16.