글 읽기 - 어떤게 더 좋은 코드일까요?

dogwdso 2년 전 0

DP프로그래밍 문제중 3kg 봉투와 5kg 봉투로 nkg을 최소 개수로 담는 문제입니다.

bag[0]=0인것을 이용하여 풀었습니다.

구할수없는 n은 -1로 출력해야 하는데

요약 하자면

DP는 bag[n]까지의 값이 정확합니다 n을 입력했을때 bag[0:n+1]까지의 값이 모두 정확하게 나오지만 , 검증하는 과정이 복잡합니다.

DP2는 bag[n]까지의 값은 정확하지 않습니다. 만약 DP[0]를 만나지 못했다면 FLAG변수로 출력자체를 -1로 해버립니다.

둘다 DP[n]을 정확한 값으로 리턴하는데 , DP2 프로그램은 DP[n]까지의 값이 틀린게 좀 있습니다. 어차피 min을 쓰기때문에 -1대신 123456789를 리턴함으로써 절대 포함되지 않도록 해줬기 때문입니다.

알고리즘을 사용할때, DP[n]까지의 값이 모두 정확해야하나요?

#include <iostream>
using namespace std;
int bag[5001];
int FLAG;
int DP(int n)
{
    if (n > -1)
    {
        if (bag[n] != -1)
            return bag[n];
        else //bag[n] == -1
        {
            bag[n] = min(rec(n - 5) + 1, rec(n - 3) + 1);
            if (bag[n] == 0)
            {
                bag[n] = max(rec(n - 5) + 1, rec(n - 3) + 1);
                if (bag[n] == 0)
                    bag[n] = -1;
            }
        }
        return bag[n];
    }
    return -1;
}

int main()
{
    int n = 0;
    cin >> n;
    for (int i = 0; i < n + 1; i++)
        bag[i] = -1;
    bag[0] = 0;
    cout << DP(n);
}

int DP2(int n)
{
    if (n == 0)
    {
        Flag = 1;
        return 0;
    }
    if (n < 0)
        return 123456789;

    if (bag[n])
        return bag[n];
    else //bag[n]==0
        bag[n] = min(rec(n - 3) + 1, rec(n - 5) + 1);

    return bag[n];
}

int main2()
{
    int n = 0;
    cin >> n;
    int ans = DP2(n);
    if (Flag == 0)
        cout << -1;
    else
        cout << ans;
}

amsminn 2년 전 0

저는 2번을 선호하는데 개취인것 같네요

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

문제

문제

출처

ICPC

어떤게 더 좋은 코드일까요?

dogwdso 2년 전 0

amsminn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말