BOJ 23560 : 약

• 문제 링크 : boj.kr/23560
• 난이도 : S2
• 태그 : DP

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    ll ans = 2;
    for(int i = 1; i < n; i++) ans *= 3;
    cout << ans;

    return 0;
}

---

풀이

우선 약봉지는 좌우 대칭이므로 처음 먹는 약을 앞에서 먹는 것으로 고정하고 생각해보자.

시뮬레이션 해보면 An-1, An-2, ... A1의 모양이 나오는 것을 확인할 수 있다.

좌우 대칭을 고정해서 계산했으므로 An = 2(An-1 + An-2 + ... A1)이다.

식을 풀면 An = 2*(n-1)^3이다.