csehyoung   8달 전

5000정도부터는 안돌아가지는데 어디가 잘못된 건지를 모르겠네요....

yukariko   8달 전

check 배열의 초기화를 0으로 설정했기 때문에 발생하는 문제입니다.

0이라는 숫자가 문제인것은 아니고, search함수가 반환할 수 있는 값을 초기화 값으로 설정한것이 문제입니다.

check에 0이 들어가면 중복 제거가 되지 않아 반복횟수가 늘어나게 됩니다.


csehyoung   8달 전

#include <iostream>
using namespace std;

int cannon[125];
int check[300002][125];
int n, p;

int search(int sum, int idx)
{
    if (sum > n)
        return 987654321;
    if (sum == n)
        return 0;
    if (idx == p)
        return 987654321;
    
    if (check[sum][idx] != -1)
        return check[sum][idx];

    check[sum][idx] = search(sum + cannon[idx], idx) + 1;
    int temp = search(sum, idx + 1);

    if (check[sum][idx] > temp)
        check[sum][idx] = temp;

    return check[sum][idx];
}

int main()
{
    cin >> n;

    for (int i = 1; i < 125; i++)
    {
        cannon[i] = i * (i + 1) * (i + 2) / 6;
        if (cannon[i] > n)
        {
            p = i;
            break;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < p; j++)
            check[i][j] = -1;
    }

    cout << search(0, 1) << endl;
}


이렇게 -1로 초기화 해줘도 똑같이 안되요...

baactree   8달 전

http://copynull.tistory.com/40

BOJ는 64M로 알고있음

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