문제
금지된 문자열이 존재하지 않는 모든 A와 B, 그리고 C로 이뤄진 길이가 N인 문자열의 수를 출력하는 프로그램을 작성하라.
금지된 문자열이란 문자열에서 "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" 와 같은 부분문자열(substring)이 존재하는 문자열이다.
예를 들어 "BAACAACCBAAA"은 금지된 문자열이나, "AABBCCAABB"는 그렇지 않다.
입력
입력은 1이상 30이하의 정수 N이 입력된다.
출력
길이 N의 올바른 문자열의 수를 출력한다. 주의 : 답이 32-bit integer 범위를 넘어갈 수 있음을 유의한다.
예제
2
9
힌트
로그인해야 코드를 작성할 수 있어요.