글 읽기 - max_element 쓰면 터지는 이유?[코드 있음]

herdson 4년 전 0

https://www.acmicpc.net/board/...

오답이 떴길래 링크의 데이터를 참조하다 못해 정답인 코드랑 거의 똑같이 쓰다시피 했는데

answer : 2013845695
now : 2146712920

계속 이렇게 나오는 겁니다...
그래서 답 출력을 dp 배열[만들어야 하는 가치 값] 으로 바꿨더니 멀쩡하게 나왔습니다.
분명 메모이제이션한 최대 값이 곧 경우의 수일 것이라 생각하고 max_element를 사용했던 것이었는데 오답을 만드는 결정적 요인이 되었던 것 같습니다.

왜 이런 결과가 나온 것일까요??

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

array<int, 10001> task{0};

int main()
{
    cin.tie(0);
    int a, range;
    task[0] = 1;
   
    cin >> a >> range;

    vector<int> coin;
    vector<int>::iterator t;
    int x;
    while (a--)
    {
        cin >> x;
        coin.push_back(x);
    }

    for (t = coin.begin(); t != coin.end(); ++t)
    {
        for (int i = *t; i <= range; ++i)
        {
            task[i] += task[i - *t]; 
        }
    }
    // correct code
    cout << task[range] << '\n';
    
    // wrong code
    //cout << *max_element(task.begin(), task.end()) << '\n';
}

djm03178 4년 전 1

"분명 메모이제이션한 최대 값이 곧 경우의 수일 것이라 생각하고"

이 문장에 대한 간단한 반례입니다. 동전이 2원짜리 한 종류만 있을 때, 9원을 만드는 경우의 수가 많을까요, 8원을 만드는 경우의 수가 많을까요?

herdson 4년 전 0

ㄴ 그런 크리티컬한 케이스를 미처 생각해내지 못했군요...

좋은 반례 제공해주셔서 감사합니다.

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

문제

문제

출처

ICPC

max_element 쓰면 터지는 이유?[코드 있음]

herdson 4년 전 0

djm03178 4년 전 1

herdson 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말