23560 약
백준이는 일 동안 약을 먹어야 한다. 약은 아침, 점심, 저녁에 한 번씩 먹어야 하고, 한 번 먹는 약은 약 봉투에 담겨있다. 약 봉투는 개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)}을 번 이어붙인 형태이다. 약을 먹을 때에는 가장 앞에 있는 약 봉투와 가장 뒤에 있는 약 봉투만 뜯어서 먹을 수 있다.
아침 약과 저녁 약은 같은 약이기 때문에, 아침에 저녁 약을 먹어도 되고, 저녁에 아침 약을 먹어도 된다. 하지만, 점심 약은 점심에만 먹어야 한다. 이런 이유 때문에 가장 앞에 있는 약부터 순서대로 먹는 방법 이외에 다른 방법도 존재한다.
이 주어진다. 약을 먹는 서로 다른 방법의 수를 구해보자.
첫째 줄에 이 주어진다.
일치 약을 먹는 서로 다른 방법의 수를 출력한다.
시간 - 1초
메모리 - 512MB
n = int(input())
result = 2 * (3 ** (n-1))
print(result)
1번 부터 3N번 까지의 약이 있을때, 1번부터 시작하거나 3N번 부터 시작하는 경우는 대칭으로 같기 때문에 1번 부터 먹었을 경우의 수만 구하면 된다.
1 -> 2 -> 3 (n-1일치와 동일)
-> 3N -> 3 -> 3N-1 -> 3N-2 (n-2일치와 동일)
-> 4 ...
과 같기 때문에
An = 2 * (An-1 + An-2 + ...) 가 된다.
여기서 An-1 = 2 * (An-2 + An-3 + ...)
=> An = 2 * (An-1 + 1/2An-1),
=> An = 3 * An-1
A1 = 2 이기 때문에
An = 2 * 3^(n-1)
이 된다.