[백준][파이썬] 23560 약

이상협·2023년 1월 13일
0

알고리즘

목록 보기
3/3

🎈문제 내용

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

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

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

입력

첫째 줄에 NN이 주어진다.

출력

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

제한

1N151 \le N \le 15
시간 - 1초
메모리 - 512MB

🎈풀이

n = int(input())

result = 2 * (3 ** (n-1))
    
print(result)

1번 부터 3N번 까지의 약이 있을때, 1번부터 시작하거나 3N번 부터 시작하는 경우는 대칭으로 같기 때문에 1번 부터 먹었을 경우의 수만 구하면 된다.

  • 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)이 된다.

0개의 댓글