글 읽기 - memset 질문드립니다.

bansh123 4년 전 1

혼자풀다 도저히안돼서 구글링해서 좀 알아봤는데...

dp 로 문제푸는건 이해를 했습니다만, 코드 주석부분 두줄에서 왜 저렇게 초기값을 설정해야 답이 올바르게 나오는지

잘 모르겠습니다..

예를들어서 왜 dp2원소들을 전부 -1로 초기화하고 첫번째 주석부분에 cache != infl 대신 cache != -1

로하면 답이 다르게나오는건지.. ㅠㅠ

가르쳐주시면 감사하겠습니다!

#include <iostream>
int64_t dp2[52][104][2],K;
int N;
const int64_t infl = 0x3f3f3f3f3f3f3f3f;
int64_t gogo(int cnt, int sum, int wrong)
{
    if (cnt == N)
        return (wrong||(sum!=0));
    int64_t& cache = dp2[cnt][sum+N][wrong];
    if ((cache) != infl) return cache; //여기에서 cache != -1로하고
    cache = 0;
    cache += gogo(cnt + 1, sum + 1, wrong);
    cache += gogo(cnt + 1, sum - 1, wrong || sum<=0);
    return cache;
}
void go2(int cnt, int sum, int wrong,int64_t k)
{
    if (cnt == N)
        return;
    if (dp2[cnt + 1][sum + N + 1][wrong] >= k)
    {
        if (cnt == N - 1 && k == 2)
            printf(")");
        else
            printf("(");
        go2(cnt + 1, sum + 1, wrong, k);
    }
    else
    {
        printf(")");
        go2(cnt + 1, sum-1, wrong || sum <= 0 , k - dp2[cnt + 1][sum + N + 1][wrong]);
    }
}
int main()
{
    memset(dp2, 0x3f, sizeof(dp2)); //여기에서 memset대신 3중포문으로 dp2 원소 다 -1로 초기화
    std::cin >> N >> K;
    gogo(0, 0, 0);
    if (K + 1 > dp2[0][N][0])
    {
        std::cout << -1;
        return 0;
    }
   go2(0, 0, 0, K + 1);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

memset 질문드립니다.

bansh123 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말