1301번 비즈 공예

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

dp 다이나믹 cache 캐시 복습 코테 코딩 필수 추천 boj 백준 동적 계획

아래 3개의 문제도 같이 풀어보길 꼭 추천한다.

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

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

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

cache[a][b][c][d][e][f][g] : 

a는 1번 공의 현재 개수

b는 2번 공의 현재 개수

.

.

e는 5번 공의 현재 개수

f는 그 전의 공 번호

g는 그 전전의 공 번호

#include<bits/stdc++.h>
 
using namespace std;
 
int n, a[7];
long long cache[11][11][11][11][11][7][7];
 
// 1번, 2번, 3번, 4번, 5번 구슬의 현재 개수와 전의 구슬 번호(before), 전전의 구슬 번호(bbefore)
long long dfs(int one, int two, int three, int four, int five, int before, int bbefore)
{
    // 모든 구슬을 모두 사용했다면
    if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0) {
        return 1;
    }
 
    // 음수가 있다면 0을 return
    if (one < 0 || two < 0 || three < 0 || four < 0 || five < 0) {
        return 0;
    }
 
    long long &ret = cache[one][two][three][four][five][before][bbefore];
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    // 1번 구슬의 개수가 1 이상이고 전과 전전의 공이 1번이 아니라면
    if (one >= 1 && before != 1 && bbefore != 1) {
        // 전(before)이 전전(bbefore)로 갈 것이고,
        // 현재(one) 공이 전(before)으로 갈 것이다.
        // bbefore은 신경 쓸 필요 없다.
        ret = dfs(one - 1, two, three, four, five, 1, before);
    }
 
    // 2번 구슬의 개수가 1 이상이고 전과 전전의 공이 2번이 아니라면
    if (two >= 1 && before != 2 && bbefore != 2) {
        ret += dfs(one, two - 1, three, four, five, 2, before);
    }
 
    // 3번 구슬의 개수가 1 이상이고 전과 전전의 공이 3번이 아니라면
    if (three >= 1 && before != 3 && bbefore != 3) {
        ret += dfs(one, two, three - 1, four, five, 3, before);
    }
 
    // 4번 구슬의 개수가 1 이상이고 전과 전전의 공이 4번이 아니라면
    if (four >= 1 && before != 4 && bbefore != 4) {
        ret += dfs(one, two, three, four - 1, five, 4, before);
    }
 
    // 5번 구슬의 개수가 1 이상이고 전과 전전의 공이 5번이 아니라면
    if (five >= 1 && before != 5 && bbefore != 5) {
        ret += dfs(one, two, three, four, five - 1, 5, before);
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
 
    memset(cache, -1, sizeof(cache));
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
 
    printf("%lld\n", dfs(a[1], a[2], a[3], a[4], a[5], -1, -1));
 
    return 0;
}