[파이썬/python] 백준 - 23560 약

문제

https://www.acmicpc.net/problem/23560

---

문제 설명

1. 백준이는 N일 동안 약을 먹어야 한다.
2. 약은 아침, 점심 저녁에 한 번씩 먹어야 하고, 한 번먹은 약은 약 봉투에 담겨있다.
3. 약 봉투는 3N개가 일렬롤 붙어있다.(아침, 점심, 저녁)을 N번 이어붙인 형태로.
4. 약을 먹을 땐 가장 앞에있는 약 봉투와 가장 뒤에 있는 약 봉투만 뜯어서 먹을 수 있다.
   1. 아침, 저녁은 같은 약이기 때문에 상관없이 먹어도 된다.
   2. 점심약은 점심에만 먹어야 한다.
5. N이 주어질 때 약을 먹는 서로 다른 방법의 수를 구해보자.

 

---

풀이

나는 이 문제가 이해가 잘 안가서 N = 1 ~ 3까지 전부 구했다.

N = 1, 2가지

N = 2, 6가지

N = 3, 18가지

... 으로 나오길래 이전 항의 3배를 해서 다음항을 구했더니 정답이었다.

 

하지만 문제 자체의 원리가 이해가 가지 않아서 구글링도하고 GPT 검색도 해서 문제를 이해했다.

 

1,2,3,4,5,6.....3N개의 약이 존재할 때 1번부터 약을 먹는 경우를 생각해보자.

 

1일부터 약을 먹어야 하기 때문에 처음에는 1-> 2순서로 약을 먹어야 한다.

그 다음은 3과 맨 뒤의 3N 두 개의 분기로 갈리게 된다.

 

계속해서 약 먹는 순서를 구해보자 

1 -> 2 -> 3

          -> 3N  -> 3 -> 3N-1 -> 3N-2

                                         -> 4 -> 3N-2 -> 5 .... 

위와 같이 반복되는 구조가 보인다.

 

1->2->3을 먼저 먹게되면 1일치 약이 전부 사라지고 남은건 4,5,6....3N이다.

하지만 3을 먹지 않고 3N을 먹게 되면 3N -> 3 -> 3N-1 -> 3N-2까지 먹게되야 하루치 약이 전부 사라지게 되고

총 2일치 약이 전부 사라지게 된다.

 

이런식으로 반복하다 보면 아래의 경우로 판단할 수 있다.

• 1일치의 약이 사라짐
• 2일치의 약이 사라짐
• 3일치의 약이 사라짐
• ...
• N일치의 약이 사라짐

이와 같은 경우를 모두 더했을 때 현재 구하려는 N일 때 먹을 수 있는 경우의 수가 나오게 된다.

 

그럼 생각해보자. A일치의 약이 사라졌을 때 남은 약은 N-A일치의 약이 된다.

 

N = 4일 때

1일치의 약을 먹었다면 3일치가 남게되고

2일치의 약을 먹었다면 2일치가 남게되고

3일치의 약을 먹었다면 1일치가 남게되고

4일치의 약을 먹었다면 0일치가 남게된다.

 

즉 부분 문제를 더해서 총 경우의 수를 구하기 위해 

$A_4 = A_3 + A_2 + A_1 + A_0$ 같은 수식을 세울 수 있다.

이를 점화식으로 변경하면

$A_n = A_{n-1} + A_{n-2} + A_{n-3} ...A_0$

 

하지만 지금까지 구한 경우의 수는 앞에서부터 먹었을 때의 경우의 수이고 뒤에서 시작하는 경우도 존재하기 때문에 2를 곱한다.

따라서 $A_n = 2(A_{n-1} + A_{n-2} + A_{n-3} ...A_0)$ 라는 수식을 세울 수 있다.

여기서 $A_{n-1} = 2(A_{n-2} + A_{n-3} + A_{n-4} ...A_0)$ 이므로 수식 $A_{n-2} + A_{n-3} + ...A_0$에 이 값을 대입하게 되면

$A_n = 2(A_{n-1} + 1/2A_{n-1})$

$A_n = 3A_{n-1}$이라는 점화식을 세울 수 있다.

 

따라서 등비수열의 구조가 반복되기 때문에 다이나믹 프로그래밍을 통해 문제를 풀이할 수 있다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [0 for _ in range(n)]
dp[0] = 2

for i in range(1,n):
    dp[i] = dp[i-1]*3

print(dp[n-1])

 

---

시간복잡도

• N은 최대 15이기 때문에 단순 O(N)의 시간복잡도를 가진다.