[백준] 23560 약 (C++)

23560번: 약

어렵지 않은 실버 dp 문제이다. 학회에 질문이 올라왔던 문제라 한 번 풀어보았다. 나는 dp로 풀었는데, 다른 동기는 등비수열 꼴의 매우 간단한 일반항으로 문제를 해결하였다. 신기해서 풀이를 써본다.

 

 

 

문제는 어렵지 않다. N일동안 아침, 점심, 저녁 약 봉투에서 약을 뜯어서 먹어야 한다. 이 때, 아침약과 저녁약은 똑같다. 약 봉투는 3N개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)}을 N번 이어붙인 형태이다. 약을 먹을 때에는 가장 앞에 있는 약 봉투와 가장 뒤에 있는 약 봉투만 뜯어서 먹을 수 있다. N일 동안 약을 먹는 서로 다른 경우의 수를 구하는 문제이다.

 

---

내 풀이

n일치의 약을 먹는 경우의 수를 An이라 하자.

 

우선 n일치의 약이 다음과 같이 있다. 파란색이 점심약이다.

설명의 편의를 위해 왼쪽부터 1, 2, 3, ... , 3N-2, 3N-1, 3N 의 번호를 부여하였다.

 

 

 

 

그렇다면 첫 날 약을 먹는 모든 경우는 4가지 뿐이다. 각 경우마다 약을 먹고 난 뒤의 약 봉투의 상태를 나타내보자.

 

 

 

(i) (1, 2, 3) 순서로 약을 먹은 경우

남은 봉투의 모양이 n-1일치의 약봉투와 같다.

 

(ii) (3N, 3N-1, 3N-2) 순서로 약을 먹은 경우

남은 봉투의 모양이 n-1일치의 약봉투와 같다.

 

 

(iii) (1, 2, 3N) 순서로 약을 먹은 경우

 

 

 

(iv) (3N, 3N-2, 1) 순서로 약을 먹은 경우

 

 

 

규칙이 보인다.

 

위에서 볼 수 있듯이 (i)과 (ii)의 경우에는 남은 봉투의 모양이 (n-1)일치의 약봉투와 같다.

 

(iii)과 (iv)의 남은 봉투의 모양은 좌우가 대칭이므로 각각 먹는 경우의 수는 같을 것이다. 그러므로 n일치의 약봉투가 (iii)이나 (iv)의 모양일 때 먹을 수 있는 경우의 수를 Bn이라고 하자.

 

 

 

이를 통해 다음과 같은 점화식을 얻을 수 있다.

 

 

이제 Bn을 구해야 한다.

이는 위에서와 비슷한 방법으로 약을 3개씩 지워가면서  직접 구해보자. 다음과 같은 점화식을 쉽게 얻을 수 있다.

 

 

 

점화식을 얻었으므로 코드를 작성하는 것은 어렵지 않다.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n;
ll a[16];
ll b[16];

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    a[1] = 2;
    b[1] = 1;
    for (ll i = 2; i <= n; i++) {
        a[i] = 2 * a[i - 1] + 2 * b[i - 1];
        b[i] = b[i - 1] + a[i - 1];
    }
    cout << a[n] << endl;
    
    return 0;
}

 

 

---

동기의 풀이

그렇다면 동기의 풀이를 보자.

 

 

약은 1번 부터 먹는 경우와 3N번 부터 먹는 경우가 있다. 이는 좌우 대칭이므로 경우의 수는 똑같다. 그러므로 n일치의 약을 1번 부터 먹는 경우만 보자.

 

이런식으로 쭉 전개된다.

 

3N부터 먹는 경우도 똑같으므로 2를 곱하면 다음과 같은 점화식을 얻을 수 있다.

 

위 식의 일반항을 구하는 과정은 다음과 같다.

 

내 풀이와 다르게 매우 깔끔한 식이 나온다 ㄷㄷ

 

코드는 다음과 같다.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n, ans = 2;

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for (ll i = 2; i <= n; i++) ans *= 3;
    cout << ans << endl;
    
    return 0;
}

 

---

 

 

 

 

 

내 풀이의 2번째 점화식이 계차수열이니까 이를 이용하여 두 점화식을 풀 수 있고, 그 결과가 등비수열이 나오는 것 같다. 아마두?

 

 

 

 

푼 사람들의 코드를 보면 이렇게 푼 사람들이 꽤 많다....

매우 신기하다. 이게 어떻게 바로 보였을까...? ㄷㄷ