시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB45428523767.714%

문제

백준이는 $N$일 동안 약을 먹어야 한다. 약은 아침, 점심, 저녁에 한 번씩 먹어야 하고, 한 번 먹는 약은 약 봉투에 담겨있다. 약 봉투는 $3N$개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)}을 $N$번 이어붙인 형태이다. 약을 먹을 때에는 가장 앞에 있는 약 봉투와 가장 뒤에 있는 약 봉투만 뜯어서 먹을 수 있다.

아침 약과 저녁 약은 같은 약이기 때문에, 아침에 저녁 약을 먹어도 되고, 저녁에 아침 약을 먹어도 된다. 하지만, 점심 약은 점심에만 먹어야 한다. 이런 이유 때문에 가장 앞에 있는 약부터 순서대로 먹는 방법 이외에 다른 방법도 존재한다.

$N$이 주어진다. 약을 먹는 서로 다른 방법의 수를 구해보자.

입력

첫째 줄에 $N$이 주어진다.

출력

$N$일치 약을 먹는 서로 다른 방법의 수를 출력한다.

제한

  • $1 \le N \le 15$

예제 입력 1

1

예제 출력 1

2

다음과 같은 순서대로 약을 먹을 수 있다.

  • (1일 아침), (1일 점심), (1일 저녁)
  • (1일 저녁), (1일 점심), (1일 아침)

예제 입력 2

2

예제 출력 2

6

다음과 같은 순서대로 약을 먹을 수 있다.

  • (1일 아침), (1일 점심), (1일 저녁), (2일 아침), (2일 점심), (2일 저녁)
  • (1일 아침), (1일 점심), (1일 저녁), (2일 저녁), (2일 점심), (2일 아침)
  • (1일 아침), (1일 점심), (2일 저녁), (1일 저녁), (2일 점심), (2일 아침)
  • (2일 저녁), (2일 점심), (2일 아침), (1일 저녁), (1일 점심), (1일 아침)
  • (2일 저녁), (2일 점심), (2일 아침), (1일 아침), (1일 점심), (1일 저녁)
  • (2일 저녁), (2일 점심), (1일 아침), (2일 아침), (1일 점심), (1일 저녁) 

출처

University > 제주대학교 > 2021 하반기 취업 알고리즘 집중특강 및 해커톤 대회 B번