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

1.

평균값이니까 x y z는 자연스럽게 차이가 일정한 수로 정해진다.

 

2.

나머지가 반복된다.

 

3.

센다.

 

4.

거리가 같은 사실을 가지고 방정식을 세운다. 거속시 문제

 

5.

이렇게 생긴 복면산의 경우 a+b+c 값을 보기에서 찾아 두고 푸는 게 빠름

a+b+c를 했는데 a가 나왔다는 말은 b+c가 10이라는 의미고

a+b+c+1이 b라는 말은 b+c가 일단 10으로 올라가면 a+1은 b라는 의미가 됨. 백의 자리도 같은 이유로 a+1는 b니까 c는 1 이상이 될 수 없어서 1이 되고, b는 9가 된다.

a는 8이 된다.

 

6.

어느 한 줄에 있는 숫자들은 아무리 교환해도 한 줄에 있다.

한 줄에 있지 않은 선택지가 정답

 

7.

어떤 점에서 한 번 갔다가 다시 돌아오려면 2번이기 때문에 짝수번 이동해야 함

0~10을 직선이라고 치면 0,2,4,6,8,10이 가능

그걸 2차원으로 바꾸고 이으면 마름모꼴이 계속 반복되는 형태가 된다

그림을 그려서 푼다

121개

 

8.

양팔 저울이 아닌 것에 주의

자루에 1~10으로 숫자를 붙이고 각 자루에서 1개 2개 ..10개 동전을 꺼내 무게를 잰다.

정상이라면 550g이 나와야 하는데 불량이 있으니까 조금 적게 나옴

만약 540g이라면 10g을 뺀 자루가 불량 이런 식으로

그래서 2번

 

9.

검, 검 -> 검-1

흰, 흰 -> 검+1, 흰-2

검, 흰 -> 검-1

 

일단 흰색 공보면 –2거나 변동 없거나 둘 중 하나라 원래 흰 공이 16개면 흰색 다 없어지고 검은 공만 남고, 15개면 흰색 공이 남는다. 그래서 A=검 B=흰

 

10.

n 1 2 3 4 ...

개수 1 4 10 16 ...

증가 3 6 9 ...

 

(n-1)*3개씩 증가함

n=11 일 때 166

 

10.

A가 100바퀴에 500분, 한바퀴 = 5분

A가 80, B는 120으로 둘이 200으로 가까워지고 있음

A가 200m/s로 돌면 100000m를 도는 것과 같고 A가 B를 처음 만난 이후 이동해야할 거리는 100000-240m라 99760/400 = 250

 

다른 방법은, A가 100번 도는 동안 B가 A위치를 지나는 경우는?

B속도가 80:120 = 1.5배 빠르기 때문에 B는 150번 지나가게 된다. 그래서 250

 

13.

i보면 a+b+C=13

ii보면 a,b가 가장 작은 경우는 각각 1,2가 되어야 하는데 그 때 c가 10이니까 1<=a<b<c<=10 이라고 할 수 있음

 

a보면 a가 1,2 중 하나. 왜냐면 3이상인 경우 b, c가 확정된다. 당장 a=3일 경우만 봐도 b, c는 4,6으로 확정됨

c보면 c는 7, 8 중 하나. 왜냐면 10인 경우 a=1, b=2로 확정, 9면 a=1, b=3 확정

b보면 b는 4. 왜냐면 3인 경우 a=2, c=8로 확정, 5면 a=1, b=7확정, 6 불가능

 

아니면 직접 해보기

1 2 10

1 3 9

1 4 8

1 5 7

2 3 8

2 4 7

2 5 6

3 4 6

중에 걸러냄

 

14.

일단 그래프에 경우의 수 다 적고 홀수 교차로를 묵어 모두 짝수로 만들면 된다.

홀-홀 연결해도 짝수고, 홀-짝-홀 연결해도 좌우를 연결하면 짝수니까 잘 고르자.

한붓 그리기는 어떤 점에 연결된 선의 개수가 홀수개면 불가능하므로 짝수개로 만들어 주어야 한다.

 

15.

1 2 라면? 1 남음

1 2 3? - 0 2 4 남음

1 2 3 4? - 1,35남음

보면 집합에 홀수의 개수가 중요함

홀수가 홀 수개에 들어있다면 남는 수에는 무조건 홀수,

홀수 짝 수개가 있다면 남는 수 무조건 짝수

 

그리고 홀수로 끝나는 경우는 마지막 홀수까지 가능

즉, [n/2] (가우스)

n=30이면 홀수가 15개라 홀수만 남음

못 만드는 수는 2 4 6 8 .. 30 다 더하면 240

 

28.

재귀적으로 2진수 변환

 

 

29.

유클리드 호제법 재귀 구현

if(n==m) return n;

if(n>m) return f(n-m,m);

else return f(n,m-n);

 

32.

2진수 변환하고 0의 개수

 

33.

f(a,b) a줄 b줄 바꾸기

g(a,b) a열 b열 바꾸기

 

34.

2014: 00000000 00000000 00000111 11011110

>>1: “ “ 00000011 11101111

|연산 하면 00000000 0000000 00000111 11111111

>>2: 00000001 11111111

|연산 하면 00000111 11111111

....

하다보면

00001000 00000000 = 2048

 

35.

직접 계산하면 바보

표를 그린다

 

b -4 -3 -2 -1 0 1 2

a

0 0 0 0 0 0 0 0

1 0 0 0 1 1 1 0

2 0 0 1 2 3 2

3 0 1 3 6 7 6

4 1 4 10 16 19

 

4,0 = 19

 

36.

a문자열의 글자랑 b 문자열의 글자를 비교해서 a가 사전 순으로 b보다 크면 1이고 작으면 –1을 출력한다.

 

37.

완전 제곱수 찾기

약수의 개수가 홀수인 수는 완전 제곱수다.

 

38.

3개씩 쪼개고 부분별로 출력

mis sis sip pi

맨 앞 문자: mssp

두번째: iiii

새번째: ssp

 

39.

f(0) =1

f(1)=f(0)*f(0)=1

f(2)=f(0)*f(1)+f(1)*f(0) = 2

...

 

41.

2014 -> 16진수보다

2014 -> 2진수 -> 4개씩 묶어 16진수 바꾸는 게 편함

2014 = 11111011110 = 111 1101 1110 = 7DE

str배열의 값이 거꾸로 출력된다.

 

42.

수직선을 그려보면 알 수 있다.

 

43.

while따라 그래프 그리면 편하다.

 

44.

달팽이 배열

 

45.

오름차순 버블정렬

 

46.

에라토스테네스의 체와 비슷하다.

자기 자신을 제외한 약수의 개수

 

47.

현재에서 하나 작은 집합(0~idx-1)에서 구한 최솟값과 arr[idx]를 비교해서 작은 값을 반환하며 반복한다.

 

48.

깊이 우선 탐색

막다른 정점이면 그 정점의 번호부터 탐색 경로를 거꾸로 출력한다.

 

49.

각 사대에서 동물을 잡을 수 있으면 잡고 카운트한다.

어떤 사대에서 동물을 잡으려면 가로로 이동해야하는 격자의 수+세로로 이동해야하는 격자의 수의 합과 같거나 작으면 가능하니까 그 사대의 x좌표에서 동물의 x좌표를 뺀 값의 절댓값+동물의 y좌표 합

 

50.

데이터를 직접 그려보기