글 읽기 - 1965 상자쌓기문제 반례를 못찾고있습니다 ... !;

polakr 5년 전 0

아이디어는 정말 상자를 쌓는 느낌으로 모든 N개의 상자를 기준으로 가능한 상자를 모두 v에 쌓아올리면서 불가능할때까지 쌓인 v의 사이즈를 최대값으로 갱신하면서 찾았는데 틀리네요 ...

#include <iostream>
#include <vector>

int N;
int arr[1001];
std::vector<int> v;
int ans = 1;

void dp(int cur) {
    for (int i = cur + 1; i <= N; i++) {
        if (arr[cur] < arr[i]) {
            v.push_back(arr[i]);
            dp(i);
            v.pop_back();
        }
        else {
            break;
        }
    }
    ans = (ans < v.size())? v.size(): ans;
}

int main() {
    std::cin >> N;
    for (int i = 1; i <= N; i++) {
        std::cin >> arr[i];
    }
    for (int i = 1; i <= N; i++) {
        dp(i);
        v.clear();
    }
    std::cout << ans << std::endl;
    return 0;
}

lovinix 5년 전 2

input

2 3 1 4 5 6

output

correct answer

일단 size는 cur자신을 포함해야하기 때문에 v.size()가 아니라 v.size()+1이 되어야하며,

else {break;} 문 때문에 cur 이후에 cur보다 작은 수가 나오면 이후를 아예 탐색하지 않게 됩니다.

또한 memoization을 활용하지 않는다면, 올바르게 짜더라도 시간초과가 날 것 같습니다.

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

문제

문제

출처

ICPC

1965 상자쌓기문제 반례를 못찾고있습니다 ... !;

polakr 5년 전 0

lovinix 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말