2016 지역대회중고등부문제 1 (1점) 어떤수 에대해등식 이성립한다고한다 이때 의값은? 1 1 2 0 3 1 4 2 5 2016 2 (12점) 1에서 20까지의자연수를모두곱한수를 X라고하자 X를 16진수로표기했을때오른쪽끝에연속적으로나타나는 0의개수는? 1 2 2 3 3 4 4 9 5 18 3 (13점) 자연수의제곱으로나타낼수있는수를제곱수라고부른다 예를들어, 1, 4, 9 등은제곱수이다 임의의자연수는여러개의제곱수의합으로표현할수있다 예를들어, 4 = 4, 5 = 4 + 1, 7 = 4 + 1 + 1 + 1 이므로 4는한개의제곱수의합, 5는두개의제곱수의합, 7은 4개의제곱수의합으로나타낼수있다 실제로 7은제곱수의합으로표현하기위해적어도 4개의제곱수가필요한제일작은자연수이다 이와같이자연수를최소개수의제곱수의합으로표현할때, 4개이상의제곱수가필요한두번째로작은자연수는? 5 (16점) 시침과분침으로시간을나타내는아날로그시계가있다 이시계로어느날오후 12시 1분부터다음날오전 10시 50분사이에시침과분침이정확하게겹치는것은총몇회인가? 1 19 2 20 3 21 4 22 5 23 6 (17점) 명의사람들이일렬로줄을서있다 이들 명의사람들을다음조건을만족하도록하나이상의그룹으로나누려고한다 (1) 각그룹은한명이상의사람이속해야한다 (2) 각그룹에속하는사람들은연속하여서있는사람들이어야한다 (3) 각사람은정확히한개의그룹에속해야한다 인경우, 위의조건에만족하도록그룹을나누는방법은총네가지이다 이라면, 가능한방법의수는? 1 8 2 14 3 16 4 28 5 32 7 (18점) 아래의그림은여러개의도시 (a,b,c,d,e,f,g,h,i) 사이에도로를건설하는비용을보여주고있다 모든도시를연결할때필요한최소비용은얼마인가? 1 11 2 12 3 13 4 14 5 15 4 (14점) 자동차의주행거리를기록하는장치는다섯자리로구성되어있다 즉, 00000km부터 99999km까지기록할수있다 00000km부터시작하여 1km씩증가하여 99999km까지도달하는동안주행장치에나타난 1의횟수는? ( 예를들면 00111km, 00112km, 00113km 에서나타나는 1의횟수는모두 7개이다 ) 1 20000 2 30000 3 40000 4 50000 5 60000 1 28 2 35 3 37 4 39 5 44
8 (2점) 다음보기중에서세자리자연수와한자리자연수의곱으로나타낼수있고, 두자리자연수와두자리자연수의곱으로도나타낼수있는가장큰수는? 1 8100 2 8910 3 8928 4 8930 5 9702 9 (22점) 두개의사각형이있을때, 이들의변과변이서로교차하여생기는교차점의최대개수는? ( 단, 교차점이무한히많은경우는고려하지않는다 ) 1 4 2 6 3 8 4 12 5 16 10 (23점) 아래그림은 A 지점과 B 지점을연결하는길을약도로표시한것이며가장작은정사각형의가로, 세로길이는모두 1이다 A 지점에서 B 지점으로이동할때에선택할수있는최단경로는모두몇가지인가? ( 사각형에서대각선으로표시된길은그사각형의가로, 세로길이보다길다는것을유의하라 ) 1 1 2 2 3 3 4 4 5 5 12 (26점) 다섯자리자연수 ABCDE에한자리자연수 F를곱해서, 여섯자리자연수 GGGGGG가되었다 여기서, A, B, C, D, E, F, G는모두 0이아니고서로다르다 그러면 C+G는얼마인가? A B C D E x F G G G G G G 1 7 2 8 3 10 4 12 5 13 13 (27점) 이세돌씨부부를포함하여총 5 쌍의부부가모임을가졌다 그들은아무도자신의배우자와는악수를하지않았고, 같은사람과두번이상악수하지도않았다 이세돌씨는아내를포함한다른사람들에게악수를몇번이나했는지물었다 놀랍게도그들모두가다다른대답을했다 그러면이세돌씨는몇번악수했을까? 1 1 2 2 3 3 4 4 5 5 1 307 2 308 3 322 4 420 5 525 11 (24점) 무게가 1, 2, 3인추를아래왼쪽그림처럼매달면저울의균형이맞게된다 아래오른쪽그림과같은저울에무게가 1, 2, 3, 4, 5인추를정확히하나씩사용하여저울이균형을이루도록매달고싶다 [*] 에매달아야하는추의무게는? 14 (1점) 다음중 C나 C++ 로된완전한프로그램에서반드시존재해야하는함수는무엇인가? 1 maine() 2 main() 3 mane() 4 manee() 5 many() 15 (1점) 다음중 C나 C++ 의연산자가아닌것은무엇인가? 1 ; 2 3 sizeof 4 ^ 5 ++
16 (1 점 ) C 나 C++ 언어로작성된아래식들중에서값이다른것은무엇인가? 1 6 ^ 2 2 3? 36 : 6 3 9 << 2 4 63 & (~27) 5 4 * 9 22 (14점) 다음프로그램의출력이소수점아래까지정확하도록하려면부분에들어가면되는코드는무엇인가? 17 (12점) while 루프와 do while 루프의최소실행횟수는각각몇번인가? 1 0번, 1번 2 1번, 1번 3 1번, 2번 4 2번, 1번 5 2번, 2번 18 (12점) 다음프로그램이실행되어 for 루프가종료된직후 x의값은얼마인가? int x; for (x=8; x>=3; x ) { float a; int b=3, c=2; a = b/c; printf("%f", a); 1 (float) 2 correct 3 (correct) 4 upgrade 5 to double 23 (15점) 다음프로그램의출력결과는무엇인가? 1 0 2 3 3 2 4 2 5 3 19 (13점) 다음연산자들중우선순위가가장높은것은? 1 + 2 / 3 % 4 > 5?: 20 (13점) 다음중컴파일이제대로되지않는문장은어느것인가? 단, a와 b는각보기에서적절한 type 변수로정의된것으로생각하라 1 b=&&a; 2 b=**a; 3 b=***a; 4 b=&a; 5 b=*a; 21 (14점) 다음배열은몇바이트를차지하는가? 단 int는 4바이트를차지하는것으로가정하라 int a, b, c, d, result; a = 4; b = 12; c = 37; d = 51; result = d % a * c + a % b + b; printf("%d", result); 1 127 2 104 3 53 4 113 5 12 24 (16점) 다음중 printf("%05d%02d", 2016, 4) 의출력결과는무엇인가? 1 020164 2 0201604 3 2016 4 4 00020164 5 0002016004 int array[30] = {1, 2, 3; 1 3 2 12 3 16 4 90 5 120
25 (16점) 다음프로그램의출력이 5가되도록할때 (a) 에들어가야할수는무엇 인가? a[18] = tmp; int num = 1, cnt = 0; while (num <= 2016) { num = num * 10 (a) ; cnt++; printf("%d", cnt); 1 0 2 2 3 4 4 6 5 8 26 (17점) 다음프로그램에서 f(6) 을한번호출하면 f(1) 은몇번호출되는가? int f(int n) { if (n <= 1) return n; return f(n 1) + 2 * f(n 2); 1 5 2 8 3 11 4 13 5 21 27 (17점) 다음프로그램을실행한후 sum의값은얼마인가? int i, j; char a[19] = "Korea\0Informatics\0"; int sum = 0; for (i = 0; i < 19; i++) { sum += strlen(a); char tmp = a[0]; for (j = 1; j < 19; j++) { a[j 1] = a[j]; 1 81 2 288 3 306 4 324 5 361 28 (18점) 다음프로그램의출력결과는무엇인가? int a[5] = {0, 1, 2, 0, 3, b[5] = {1, 2, 4, 3, 4; int c[5][5]; int i, j, k; for (i = 0; i < 5; i++) { for (j = 0; j < 5; j++) { if (i == j) c[i][j] = 0; else c[i][j] = 99; for (i = 0; i < 5; i++) { c[a[i]][b[i]] = 1; for (k = 0; k < 3; k++) // 주의 : k < 3 for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) if (c[i][j] > c[i][k] + c[k][j]) c[i][j] = c[i][k] + c[k][j]; printf("%d", c[0][4]); 1 0 2 1 3 2 4 3 5 99
29 (18점) 길이가 n인수열 a[1], a[2],, a[n] 이있다 당신은이수열에서최소 한의수를제거하여감소하지않는수열을만들려고한다 다음프로그램은제거해야 할수의개수의최솟값을출력하는프로그램이다 이때 (a), (b) 에들어갈내 용중알맞은것은? int n = 10; int a[11] = {0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7; int D[11] = {0,, lastmin[11] = {0,, r = 0; int i; for (i = 1; i <= n; i++) { if (r == 0 a[i] < lastmin[1]) D[i] = 1; else { int left = 1, right = r, mid; while (1) { mid = (a) ; if (left >= right) break; if (lastmin[mid] <= a[i]) left = mid; else right = mid 1; D[i] = mid + 1; if (D[i] > r) { lastmin[d[i]] = a[i], r++; else if (lastmin[d[i]] > a[i]) lastmin[d[i]] = a[i]; printf("%d", (b) ); (a) (b) 1 (left + right) / 2 n r 2 (left + right + 1) / 2 n r 3 (left + right) / 2 r 4 (left + right + 1) / 2 r 5 (left + right) / 2 D[n] [30 31] 다음프로그램을보고물음에답하시오 int check[101] = {0,, m = 100; int n = (a) ; int a[100] = (b) ; int i, j, p = 0; for (i = 0; i < n; i++) { check[a[i]]++; for (i = 1; i <= m; i++) { int cnt = 0; for (j = i; j <= m; j += i) { cnt += check[j]; if (cnt >= 2) p++; 30 (2점) 다음보기중프로그램실행후 p의값이가장큰것은무엇인가? (a) (b) 1 2 {49, 49 2 3 {8, 9, 10 3 4 {12, 15, 18, 20 4 5 {5, 10, 15, 20, 25 5 6 {2, 3, 5, 7, 11, 13
31 (2 점 ) 이프로그램의시간복잡도로가장적합한것은무엇인가? 34 (22 점 ) 다음프로그램의출력결과는무엇인가? 1 O(n) 2 O(n log(n)) 3 O(n + m log(m)) 4 O(n 2 + m) 5 O(n + m 2 ) 32 (2점) 다음중 을구하기위해필요한식은? int f(int a){ return a <= 1? a : f(a 1) + f(a 2); 1 f(n) 2 f(n+1) 3 f(2*n 1) 4 f(2*n) 5 f(2*n+1) 33 (22점) 다음프로그램의출력결과는무엇인가? int i, j, k, sum, a[2][2]; a[0][0] = a[1][1] = 1; a[1][0] = a[0][1] = 2; sum = 0; for (i = 0; i < 2; i++) { for (j = 0; j < 2; j++) { for (k = 0; k < 2; k++) { a[i][j] = a[j][k]; sum += (i * j * k) * a[i][k]; printf("%d\n", sum); 1 0 2 1 3 2 4 3 5 4 int i, j, a[5], b[5], s; a[0] = 2; b[0] = 0; s = 0; for (i = 1; i < 5; i++) { a[i] = a[i 1] * i; b[i] = b[i 1] + a[i]; for (i = 0; i < 5; i++) { for (j = 0; j < 5; j++) { s += a[i] * b[j]; printf("%d\n", s); 1 520 2 6072 3 6256 4 6732 5 6936 35 (23점) 다음프로그램의출력결과는무엇인가? int i, j, t, a[3]; a[0] = 2; a[1] = 0; a[2] = 1; for (i = 0 ; i < 3; i++) { t = i; for (j = 1 ; j <= 7777; j++) t = a[t]; printf("%d ", t); printf("\n"); 1 0 1 2 2 1 2 0 3 1 0 2 4 2 0 1 5 2 1 0
36 (23 점 ) 다음프로그램은 1 보다큰정수 n 을입력받고무엇을출력하는가? 38 (24 점 ) 아래와같은함수 f 와 g 가있을때, g(3, 5) 의값은무엇인가? int i, j, x, n; scanf("%d",&n); x = 1; for (i = 2; i <= n; i++) { for (j = 2; j * j <= i; j++) { if (i % j == 0) break; if (j * j > i) x = i; printf("%d\n", x); int f(int x, int y) { if (x <= 1 y <= 1) return 1; return f(x 1, y 2) + f(x 2, y 1); int g(int x, int y) { if (x <= 1 y <= 1) return 1; return g(x, y 1) + g(x 1, y) + f(x 1, y 1); 1 16 2 20 3 24 4 28 5 32 1 n 이하인소수의개수 2 n의약수의개수 3 n 이하인합성수의개수 4 n 이하인가장큰소수 5 n 이하인가장큰합성수 37 (24점) 다음은 1부터 n까지의숫자가적힌카드중에서 m개의카드를고르는경우 의수를구하는함수의일부이다 고른카드는순서를고려하지않는다고가정할때, 빈칸에들어갈내용으로알맞은것은? int f(int n, int m) { if (n < m) return 0; if (m == 0) return 1; return ; 1 f(n, m 1) + f(n 1, m) 2 f(n, m 1) + f(n 1, m 1) 3 f(n, m 1) + f(n, m 2) 4 f(n 1, m) + f(n 2, m) 5 f(n 1, m) + f(n 1, m 1) [39 40] 다음프로그램을보고질문에답하시오 const int N = 100; int edges[n][n], cnt[n]; int stack[n], out[n]; bool seen[n]; void addedge(int x, int y) { edges[x][++cnt[x]] = y; edges[y][++cnt[y]] = x; int main() { addedge(1,2); addedge(1,3); addedge(2,1); addedge(2,4); addedge(3,1); addedge(4,2);
int i, sum = 0; for(i=1;i<=4;i++) sum += cnt[i]; printf("sum = %d\n",sum); int top, n = 0; stack[top=1] = 2; while(top) { int node = stack[top ]; out[++n] = node; for(i=1;i<=cnt[node];i++) { int next = edges[node][i]; if(!seen[next]) seen[stack[++top] = next] = true; for(i=1;i<=n;i++) printf("%d ", out[i]); return 0; 40 (26점) 둘째줄에출력되는내용은? 1 1 2 4 3 2 1 2 3 4 3 2 1 3 4 4 2 1 4 3 5 2 4 2 1 3 41 (26점) 다음프로그램의출력결과는무엇인가? const int N = 1000; int a[n+1]={0,, i, j; for(i=1;i<=n;i++) { a[i] += i; for(j=i*2;j<=n;j+=i) a[j] += a[i]; printf("%d\n", a[504]); 1 3813 2 6256 3 10735 4 10737 5 31799 [42 43] 다음과같은문제를해결하기위해프로그램을작성하였다 물음에답하시오 39 (25 점 ) 첫줄에출력되는 sum 의값은? 1 3 2 4 3 6 4 8 5 12,
, 5, 2, 5 6, 7 9 6 3, 7 3 표준입력의한줄에직사각형변의길이를나타내는두정수 과 이차례로주어진다 5 입력에서주어진변의길이를갖는직사각형모양의종이를제시한규칙에따라잘랐을때생긴조각의최소개수를표준출력한줄에출력한다 1 6 5 #include <stdioh> #include <algorithm> #define Min(a,b) ((a)>(b)?(b):(a)) int W, H; int R[10005][105]; int main(){ scanf("%d %d", &W, &H);
if(w < H) std::swap(w, H); for(int i = 1; i <= W; i++) for(int j = 1; j <= H; j++) { R[i][j] = 1e9; if(i == j) R[i][j] = 1; else if ( (a) ) R[i][j] = R[i j][j] + 1; else{ for(int k = 1; k < i; k++) R[i][j] = Min(R[i][j], (b) ); for(int k = 1; k < j; k++) R[i][j] = Min(R[i][j], (c) ); 43 (27점) 다음중 (b) 와 (c) 에들어갈내용으로알맞은것은? (b) (c) 1 R[k][j] R[i][k] 2 R[i k][j] + 1 R[i][j k] + 1 3 R[k][j]*R[i k][j] R[i][k]*R[i][j k] 4 R[i][k]+R[k][j] R[i][k]+R[k][j] 5 R[k][j]+R[i k][j] R[i][k]+R[i][j k] 44 (28점) [ 단답형 ] 아래색칠된것은철판으로만든다각형이다 이모양을레이저를 이용하여몇개의조각으로절단하려고한다 레이저는최대두번까지사용할수있 는데한번은수평방향으로자르고다른한번은수직방향으로잘라야한다 최대몇 개의철판조각을만들수있을까? ( 철판은고정되어있어서한번자른후철판조각 을이동하거나겹쳐서자르는것은불가능하다 ) printf("%d\n", R[W][H]); return 0; 42 (27 점 ) 다음중 (a) 에들어갈내용으로알맞은것은? 1 i < j 2 i > j 3 j*j 3*i <= 0 4 2*i >= j 5 2*j >= i 45 (3점) [ 단답형 ] 열자리자연수 N이있다 N의가장왼쪽자리에는 N의자리값중에서 0의개수, 그다음자리값은 1의개수, 그다음자리값은 2의개수, 마지막자리값 ( 가장오른쪽자리값 ) 은 9의개수가된다 N의 0이아닌자리의값을모두곱하면얼마인가?
46 (28 점 ) [ 단답형 ] 다음프로그램의출력결과는무엇인가? 47 (28 점 ) [ 단답형 ] 다음프로그램의출력결과는무엇인가? int f(int a) { int i = 0, cnt = 0; for (i = 1; i <= a; i++) { if (a % i == 0) cnt++; return cnt; int main() { int i, sum = 0; for (i = 1; i <= 20; i++) { sum += f(i); printf("%d", sum); return 0; int f(int a) { int b = 0; while (a!= 0) { b = b * 10 + a % 10; a /= 10; return b; int main() { int i, sum = 0; for (i = 1; i <= 99; i++) { sum += f(i); printf("%d", sum % 1000); return 0;
48 (3점) [ 단답형 ] 다음프로그램의출력결과는무엇인가? int a[2][2] = {{1,1,{1,0; int b[2][2] = {{1,0,{0,1; int c[2][2] = {{0,0,{0,0; int n = 10; while (n) { if (n & 1) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { c[i][j] = 0; for (int k = 0; k < 2; k++) c[i][j] += a[i][k] * b[k][j]; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) b[i][j] = c[i][j]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { c[i][j] = 0; for (int k = 0; k < 2; k++) c[i][j] += a[i][k] * a[k][j]; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[i][j] = c[i][j]; n /= 2; printf("%d",b[0][1]); 49 (3점) [ 단답형 ] 다음프로그램의출력결과가 7이되는양의정수 n의개수는몇개인가? int n, m = 0; while (n!= 1) { if(n % 2 == 0) n /= 2; else n = 3 * n + 1; m++; printf("%d", m); 50 (3점) [ 단답형 ] 다음프로그램에서 f(0, 0) 함수를한번호출한후 cnt의값은얼마인가? int cnt, check[5][5]; int dx[3] = { 1, 0, 1, dy[3] = {0, 1, 0; void f(int x, int y) { if (x < 0 y < 0 x >= 5 y >= 5) return; if (check[x][y]) return; if (x == 4 && y == 4) { cnt++; return; check[x][y] = 1; int i; for (i=0; i<3; i++) f(x + dx[i], y + dy[i]); check[x][y] = 0;