정보올림피아드 초등 - 지역예선] 2009년도 26번문제

 

26.아래와 같은 함수 f가 있다고 하자. f(1, 1025)를 실행했을 때, 함수 f가 호출되는 횟수는 총 몇 번인가?

 

문제 풀이) 우선 실행 되는 규칙을 찾는다.

f(1,1) 인경우는 if (n == 1) return; 문장에서 리턴 되므로 한번 수행 된다.

f(1,2) 인 경우는

f(s, s + n / 2 - 1);

f(s + n / 2, e);

문장에서 f(1,1); 과 f(2,2) 를 호출 한다.

F(1,3) 은 f(1,1) 과 f(2,3) 을 호출 하고 f(2,3) 은 f(2,2) 와 f(3,3) 을 호출한다.

이렇게 찾은 규칙을 살펴 보면

f(1,1) => 1회

f(1,2) => 3회

f(1,3) => 5회

위와 같은 규칙이 성립함을 알 수 있다.

따라서 f(a,b) 에서 f 함수를 실행하는 횟수는 (b-a) * 2 + 1 과 같은 규칙이 있다는 것을 확인 할 수 있다.

이 규칙이 맞는지 f(3,4) 를 수행 시켜 보면 (4-3) * 2 + 1 = 3회가 성립하는지 확인 한다.

F(3,4) 는 f(3,3)과 f(4,4) 를 호출 함으로 총 3회를 수행 함을 확인 할 수 있다.

따라서 f(1,1025) 를 수행했을 때 f가 호출되는 총 횟수는 (1025 – 1) * 2 + 1 = 2049 임을 알 수 있다.

정답)3 번