골랜디 #7 10422번

Published at: 2025-03-25

Last modified at: 2025-03-25

오늘 푼 문제

안녕하세요 한라나입니다.
생활패턴 정상화를 노리고 저녁 시간에 골랜디를 하고 있는 저네요.
오늘 문제는 아래와 같습니다.

골드 4인데! dp인데! 저는 왜 못푸는걸까요???
다행히도 기숙사 룸메가 풀이법을 찾아내서 풀 수 있었습니다.

ST가 새로운 문자열이 될 수 있다고 모든 조합을 다 해보면, () ()()()와 ()() ()() 등을 구분하지 못하는 문제가 생깁니다.
그래서 일명 ‘큰 괄호 법칙’이라고, ()__... + (__)__... + (____)__... 를 괄호가 전체를 덮을 때까지 하는 방식으로 진행하니까 겹치는 문제가 없어졌어요!
그러니까 길이 L에 대해 문자열 갯수를 나타내는 함수 $f(L)$ 은
$f(L)=2\times f(L-2)+f(2)\times f(L-4)+f(4)\times f(L-6)+ …+f(L-4)\times f(2)$
가 되는겁니다.
점화식이니까 dp로 풀면 됩니다.
그 코드가 아래와 같습니다.

long long int solve(long long int a) {
    if(a%2==1) return 0;
    if(a==2) return 1;
    if(dp[a]!=0) return dp[a];
    long long int i;
    dp[a] += solve(a-2) * 2;
    for(i=2;i<a-2;i=i+2) {
        dp[a] += solve(i)*solve(a-i-2);
        dp[a] %= 1000000007;
    }
    dp[a] %= 1000000007;
    return dp[a];
}

저는 dp가 싫어요. 풀이과정 찾아내는건 어려운데, 막상 찾고나면, 진짜 별게 없어서 쓸 게 없습니다.

감사합니다.

---

전체 코드

#include <stdio.h>

//using namespace std;

long long int dp[5500];

long long int solve(long long int a) {
    if(a%2==1) return 0;
    if(a==2) return 1;
    if(dp[a]!=0) return dp[a];
    long long int i;
    dp[a] += solve(a-2) * 2;
    for(i=2;i<a-2;i=i+2) {
        dp[a] += solve(i)*solve(a-i-2);
        dp[a] %= 1000000007;
    }
    dp[a] %= 1000000007;
    return dp[a];
}

int main() {
    long long int n;
    scanf("%lld", &n);
    long long int i, a;
    for(i=0;i<n;i++) {
        scanf("%lld", &a);
        printf("%lld\n", solve(a));
    }
    return 0;
}