정올 2011년 중고등부 예선 풀이
- 어떤 밭을 일구는데, 세 사람 A, B, C가 혼자 밭을 일구면 각각 2시간, 3시간, 6시간이 걸린다. A, B, C 세 사람이 함께 이 밭을 일구면 몇 시간이 걸리는가?
[풀이]: A가 시간 당 1/2, B는 1/3, C는 1/6 만큼 일한다. 따라서 A,B,C가 동시에 일하는 건 hour(A+B+C) = 1이므로 hour = 1 - 아버지와 아들의 나이 합은 85이다. 과거에 아버지가 아들의 나이였을 때, 아버지의 나이는 아들의 나이의 6배이었다. 아버지와 아들의 나이 차는 얼마인가?
[풀이]: a: 아버지의 나이, b: 아들의 나이. a+b=85, a-x = 6(b-x) = b를 계산하면 a=55, b=20이므로 a-b=25이여서 답은 4번(25)가 된다. - (13)13의 마지막 끝 자리 수는 무엇인가?
[풀이]: 13을 곱하다 보면 3, 9, 7, 1의 규칙성이 생긴다. 13 mod 4 = 1. 따라서 답은 2번(3)이다. - 두 자연수의 곱이 1000일 때, 가능한 두 자연수 합의 최소값은?
[풀이]: 1000을 소인수분해 해보면 2^3 + 5^3이다. 두 자연수 합이 최소가 되려면 그 둘의 간격이 최소로 되야 하므로 잘 해보면 25와 40가 최소여서 답이 65이다. 따라서 2번이 정답. 다음을 모두 만족하는 가장 작은 양의 정수를 7로 나눈 나머지는?
2로 나누면 나머지가 1이다.
3으로 나누면 나머지가 2이다.
4로 나누면 나머지가 3이다.
5로 나누면 나머지가 4이다
6으로 나누면 나머지가 5이다
[풀이]: 2,3,4,5,6의 최소 공배수인 60에 -1을 하면 구할 수 있다. 59 mod 7 = 3이므로 답은 3번(3).다음과 같이 나열된 정수 쌍 들이 있다,
(1,1), (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), (3,2), (2,3), (1,4), (5,1), ...
위에서 (9,3)은 몇 번째로 나타나는가?
[풀이]: 군수열 문제인데 (1항) - 1개, (2,3항) - 2개, (4,5,6항) - 3개, (7,8,9,10항) - 4개 ... 따라서 [1그룹,10그룹] 까지는 총 55개이고 56번째: (11,1), 57번째: (10,2), 58번째: (9,3)이다. 답: 4번
[풀이]: 가장 큰 정사각형의 한 변의 길이를 4라 하면 A의 넓이는 16 - 4π, B의 넓이는 4π-8, C는 4, D는 π이므로 D의 면적이 가장 작다. 답: 4번7명의 학생 A, B, C, D, E, F, G에 대하여 서로 키를 비교하여 다음과 같은 결과를 얻었다.
1) A는 G보다 크다. 2) D는 B보다 크다.
3) C는 F보다 크다. 4) D는 F보다 크다.
5) G는 B보다 크다. 6) A는 D보다 크다.
7) B는 C보다 크다. 8) C는 E보다 크다.
위의 결과로부터 7명의 학생들 중 자신이 몇 번째로 키가 큰지 알 수 있는 학생들은 모두 몇 명인가?
[풀이]: 다음을 부등식으로 나타내면 A>G,D>B>C>E,F 이므로 A,B,C만이 자신이 몇 번째로 큰지 알 수 있다. 따라서 4번(3명)- 두 양의 정수 a, b의 공약수가 1만 있으면 이 두 수 a와 b는 서로소라고 한다. 예를 들어 3과 8은 서로소이고, 1과 10도 서로소이다. 10이하의 양의 정수 중에서 10과 서로소인 양의 정수들은 1, 3, 7, 9의 4개가 있다. 그러면 105이하의 양의 정수 중 105와 서로소인 것은 모두 몇 개인가?
[풀이]: 105와 서로소의 개수는 105와 합성수의 개수를 빼주면 된다. 105 = 3x5x7 이므로 (105이하의)3의 배수: 35개 + 5의 배수: 21개 + 7의 배수: 15개 - 15의 배수: 7개 - 35의 배수: 3개 - 21의 배수: 5개 + 105의 배수: 1개 = 57개
105 - 57 = 48. 따라서 답은 3번(48)이다. 4사람 A, B, C, D가 달리기 시합을 하였다. 시합이 끝난 후, 각 사람은 경기결과에 대하여 두 가지 대답을 하였다.
A: C는 2등을 하였다. B는 1등을 하였다.
B: D는 4등을 하였다. A는 2등을 하였다.
C: B는 2등을 하였다. D는 3등을 하였다.
각 사람이 말한 2개의 대답 중 하나는 참이고, 다른 하나는 거짓일 때, C는 몇 등을 하였는가? 단, 4사람의 순위는 모두 다르다.
[풀이]: 약간 백트래킹처럼 풀면 되는 문제다. 해보면 A의 두 번째 말, B의 두 번째 말, C의 두 번째 말이 맞으므로 전체 순위는 B - A - D - C가 되기 때문에 답은 4번(4)이다.어떤 반의 회장 후보로 나온 세 사람 A, B, C에 대하여 이 반 학생들의 호감도 조사를 하였다. 이 반의 학생들은 A, B, C 중 자기가 좋아하는 사람들의 순서대로 1, 2, 3의 순위를 매겼다. 단, 각 학생은 A, B, C에 대하여 같은 순위를 매길 수는 없다.
조사 결과가 다음과 같았다.1) 순위 조사에 참여한 학생들은 모두 30명이다.
2) A에게 3순위를 준 학생은 없다.
3) B보다 A를 좋아하는 학생들은 22명이다.
4) C보다 A를 좋아하는 학생들은 20명이다.
이 때, A에 1순위를 준 학생의 수는?
[풀이]: A에게 3순위를 준 학생은 없기 때문에 A에 1순위를 준 학생 = A를 뽑아준 학생 - A에게 2순위를 준 학생이다.
3)에 의해 B를 A보다 좋아하는 학생은 30 - 22 = 8명이고 4)에 의해 C를 A보다 좋아하는 학생은 30 - 20 = 10명이다.
결론적으로 A에 1순위를 준 학생 수는 30 - 8 - 10 = 12명이다. 따라서 답은 5번(12)- 1번부터 100번까지 번호가 붙여진 사람들이 있다. 또한 1부터 200번까지 번호가 붙여진 전구가 있다. 처음에 모든 전구는 꺼져 있다. 번호 1번 사람부터 100번 사람까지 100명의 사람들이 차례대로 다음과 같이 작업을 수행한다: 자기 자신의 번호의 배수가 되는 모든 전구 번호에 대하여 이 전구가 꺼져 있으면 켜고, 켜져 있으면 끈다. 이 작업이 모두 끝난 후, 마지막에 켜져 있는 전구는 모두 몇 개인가?
[풀이]: 1~100까지 약수의 개수가 홀수이면 켜져 있기 때문에 제곱수들이 켜져 있는다.(10개)
101~200까지는 학생들의 숫자는 100까지만이기 때문에 101부터는 약수의 개수가 n - 1번 껐다켜진다.
따라서 첫 번째와는 반대로 제곱수들이 빠지게 된다. 11^2, 12^2, 13^2, 14^2 총 4개이므로 100 - 4 = 96
그래서 답은 106개, 3번이다. 16개의 점이 아래와 같이 놓여 있다. 점선으로 이은 두 점사이의 거리가 모두 같다고 할 때, 서로 다른 세 개의 점으로 만들 수 있는 직각 이등변 삼각형의 개수는 모두 몇 개인가?
[풀이]: 일일이 계산하면 되는데 등변의 길이가 루트2짜리와 루트 5짜리 루트10짜리를 생각해야 한다. 그래서 다 계산하면 96개이다.●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
- 1, 2, 3의 숫자들로 나열한 길이가 6인 수열 중에서 서로 인접한 두 수의 차이가 1이하인 수열은 몇 개인가? 예를 들어, 길이가 6인 수열 1, 2, 3, 2, 1, 1은 인접한 모든 두수의 차이가 1이하이지만, 길이가 6인 수열 1, 3, 2, 2, 1, 1는 아니다.
[풀이]: DP[순번][이전숫자]
DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] + DP[i - 1][j + 1]
DP[1][1] = DP[1][2] = DP[1][3] = 1
DP[2][1] = 2, DP[2][2] = 3, DP[2][3] = 2
DP[3][1] = 5, DP[3][2] = 7, DP[3][3] = 5
DP[4][1] = 12, DP[4][2] = 17, DP[4][3] = 12
DP[5][1] = 29, DP[5][2] = 41, DP[5][3] = 29
DP[6][1] = 70, DP[6][2] = 99, DP[6][3] = 70
70 + 99 + 70 = 239이므로 1번이다. - 각 노드의 왼쪽 부트리와 오른쪽 부트리의 높이의 차이가 1이하인 이진트리를 높이균형트리라 한다. 높이가 8인 높이균형트리의 최소 노드 수는 얼마인가? 단 비어 있는 이진트리의 높이는 0이고, 1개의 노드로 이루어진 이진트리의 높이는 1이다.
[풀이]: 점화식 세우기...
높이 1) 1개
높이 2) 2개
높이 3) 4개
높이 4) 7개
높이 5) 12개
높이 6) 20개
...
이렇게 An = An-1 + An-2 + 1이 된다. +1이 되는 이유는 n = 3부터 루트 노드를 제외한 양쪽 서브 트리들은 이전 2개 것에서 가져오게 되는데 거기서 루트 노드의 개수를 더 해주면 되기 때문에 An = An-1 + An-2 + 1의 점화식이 나오게 되는 것이다.
댓글