KOI 2016 지역본선 - 단답형

단답형이 복구 불가의 수준으로 망했다....이것만 아니었으면 전국대회 가능성이라도 볼 수 있지 않았나 생각한다. 하지만 뭐, 망친 것도 나니까 탓하진 않는다.

44. 

왜 저렇게 그어야만 되는가라고 물으면 직관이라고 밖에 할 말이 없다. (적어도 본인은 그렇다.)

대회 당시에도 저렇게 그었고, 지금도 저렇게 그었는데 그 당시 답은 5고 지금은 9다. 

선을 하나 덜 그으면 5가 되는데, 그걸 쓴건지. 시간 안에도 다 못풀고, 지역본선을 그냥 정신을 놓은 상태로 푼게 아닌가 싶다.

47.

코드를 읽어보면 f(n) 은 n의 자리들을 좌우대칭시킨 값을 반환해준다. (ex - 1134 -> 4311)

i 가 1부터 99까지 증가한다. 한 자리를 대칭시키면 같은 수가 되고, 두 자리를 대칭시키면 두 자리가 된다는 생각으로 일대일 대응 함수로 생각, 수열의 합을 이용해 99*100/2 = 4950 으로 할 수 있다. 본인은 이렇게 생각했다가 낭패를 봤는데, 더 생각해보면 두 자리를 대칭시킬 때 두 자리가 되지 않을 수 있어서 일대일 대응이 되지 않는다.

10 -> 01 = 1, 20 -> 02 = 2 와 같이 두 자리에서 한 자리로 대응된다. 즉, 일대일 대응이 아닌 일대일 함수이다.

이를 생각해 9*10/2 * 10 을 4950에서 빼주고, 9*10/2를 4950에 더해주어야 한다. 9*10/2 * 9 = 405, 4950 - 405 = 4545

4545 % 1000 = 545, 답은 545 이다.

48.

주어진 코드를 읽으면 행렬 A와 행렬 B가 주어지고 다음 연산을 반복하라는 것이다.

n = 10

while( n > 0 ) {

if (n % 2 == 1){

B = AB

}

A = A^2

n /= 2

}

printf("%d", b12);

While 내부를 시행하고 행렬 B의 1행 2열의 원소를 출력하라는 문제. 행렬의 곱셈만 잘해주면 됐던 문제이다.

n = 10 : A = {2 1} {1 1}

n = 5 : B = {2 1} {1 1}, A = {5 3} {3 2}

n = 2 : A = {34 21} {21 13}

n = 1 : B의 1행 2열 원소 = 55 (이후의 A행은 출력에 영향을 안주므로 계산 안해도 무방)

따라서 답은 55