규칙을 찾아 문제를 풀어 보자

① 8 ② 10 ③ 12 ④ 15 ⑤ 18

 

 

12. n = 10일 때, KOI 수열은 몇 가지인가?

① 140 ② 141 ③ 142 ④ 143 ⑤ 144

 

 

정답) 11- 3,12-4

문제풀이)

이렇게 계산하기에는 10개를 모두 계산하기 힘들다.

따라서 끝나는 경우를 생각해 보자.

1로 끝나는 경우는 0 으로 끝나는 경우 1가지만 올 수 있다.

2로 끝나는 경우는 1로 끝나는 경우 1가지만 올 수 있다.

3으로 끝나는 경우는 0으로 끝나는 경우 1가지, 2로 끝나는 경우 1가지 이므로 2가지가 된다.

4로 끝나는 경우는 1로 끝나는 경우 1가지,3으로 끝나는 2가지에서 올 수 있으므로 3가지

5로 끝나는 경우는 0,2,4 에서 끝나는 경우에서 올 수 있으므로 1 + 1 + 3 = 5

6으로 끝나는 경우는 1,3,5 로 끝나는 경우에 6을 붙일수 있으므로 1+2+5 = 8

7로 끝나는 경우는 0,2,4,6 으로 끝나는 경우이므로 5+8 = 13 (0,2,4로 끝난 경우의 합은 5로 끝난 합과 동일하므로)

8로 끝나는 경우는 1,3,5,7 으로 끝나는 경우이므로 8+13=21

9로 끝나는 경우는 0,2,4,6,8 로 끝나는 경우이므로 13 + 21 = 34

10으로 끝나는 경우는 1,3,5,7,9 로 끝나는 경우이므로 21+34 = 55

따라서 1부터 10까지 끝나는 경우의 합을 구하면 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143