수열의 갯수 구하기

출처 : 정보올림피아드 2012년 중등부 14번문제

 

정답 : 239

문제풀이)

두 수의 차이가 1이기 때문에 다음과 같이 생각해 볼수 있다.

첫째자리 1,2,3 이 올 수 있다.

둘째자리는 첫째자리가 1인 경우 1,2 첫째자리가 2인 경우 1,2,3 첫째자리가 3인 경우 2,3 이 올 수 있다.

이렇게 생각해 보면 끝나는 경우를 테이블로 그려 볼 수 있는데 다음과 같이 그려 볼 수 있다.

마지막 자리수가 1,2,3 으로 끝나는 경우 1번째 자리,2번째자리,3번째 자리 로 생각해 보면

2번째자리 1로 끝나기 위해서는 첫째자리 1,2 에서 가능하므로 2가지

2번째자리 2로 끝나기 위해서는 첫째자리 1,2,3 모두 가능하므로 3가지 경우

2번째 자리 3으로 끝나기 위해서는 첫째자리 2,3 에서 가능하므로 2가지

이렇게 테이블을 생성해 보면

6번째에서 1로 끝날수 있는 경우 70, 2로 끝날 수 있는 경우 99가지,3으로 끝날 수 있는 경우 70가지 이므로 

70 + 99 + 70 =  239