글 읽기 - 주어진 테스트 케이스는 틀린 것 같은데 제출 시 정답으로 나와서 질문드립니다.

iskang5532 3년 전 0

테스트 케이스:

정답:

1
5
67863915

출력된 값:

7266601
5
5578883620742447096

9번 줄에서 배열 dp의 값을 0으로 초기화 하였을 때는 이상적인 값이 출력되지만, 올려놓은 코드와 같이 초기화하지 않는다면 다른 값이 출력됩니다. 문제는 이 코드 또한 정답이라고 나오네요. 혹시 이유를 아시는 분이 계실까요?>

#include <iostream>

using namespace std;

// return [max_front]C[max_backend]
long long combinate(int max_front, int max_backend)
{
    // 최대 30 x 30 (편의를 위해 31 x 31)
    long long dp[31][31];

    // [front]C[backend]
    // 1 ~ 최대치
    for (int front = 1; front <= max_front; front++)
    {
        // 1 ~ front or 구하려는 값까지 (2C3같은 현상이 발생하면 안되기 때문)
        for (int backend = 1; backend <= min(front, max_backend); backend++)
        {
            // backend의 값이 1일 경우 (4C1같은 경우일 경우 4)
            if (backend == 1)
                dp[front][backend] = front;
            else // 그 외 (backend > 1)
            {
                // 2C3과 같은 경우일 경우 0
                if (front < backend)
                    dp[front][backend] = 0;
                // 정상적인 값이 들어온 경우
                else
                    // [front]C[backend] = [front - 1]C[backend - 1] + [front - 1]C[backend]
                    dp[front][backend] = dp[front - 1][backend - 1] + dp[front - 1][backend];
            }
        }
    }
    // 입력된 컴비네이션 값 반환
    return dp[max_front][max_backend];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 테스트 케이스의 개수
    int n;
    cin >> n;

    // 각 위치의 사이트(다리를 연결할 수 있는 구역) 개수
    int a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        // 컴비네이션 실시
        // a를 기준으로 정함 (a를 모두 사용하여 b를 채우는 방법의 경우를 구하는 문제. => [b]C[a])
        cout << combinate(b, a) << "\n";
    }
}

Green55 3년 전 1

https://www.secmem.org/blog/20...

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

문제

문제

출처

ICPC

주어진 테스트 케이스는 틀린 것 같은데 제출 시 정답으로 나와서 질문드립니다.

iskang5532 3년 전 0

Green55 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말