글 읽기 - 출력부분에서 min_element를 썼더니 오답이 나옵니다 .

lisagamer 2년 전 0

다른 테스트 케이스 다 집어넣어도 맞게 나오고, 로직도 틀린 부분이 없는 것 같은데 왜그럴까 싶었습니다.

dp 테이블을 2차원 배열로 만들어서 dp[i][0]은 R 선택했을 때 최소비용, dp[i][1]은 G 선택했을 때, dp[i][2]는 B 선택했을 때의 최소비용입니다.

최소비용을 뽑아내기위해서 마지막에 *min_element(dp[N-1], dp[N-1]+2)를 사용했었는데, 제가 vs에서 테케 넣어봤을 때는 정삭적으로 출력이 됐습니다. 근데 백준에 제출을 해보니 오답이 계속 나와서, 뭔가 이부분에 문제가 있나 싶어서 아래와 같이 그냥 반복 돌면서 최소값을 찾았는데요, 통과가 됐습니다. 어떤 차이가 있는걸까요? min_element의 인자에 이터레이터를 넣어야하는데 그렇지 않아서 그런가요?

// 틀린 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <array>
#include <fstream>

#define ll long long

using namespace std;

int N;

int rgb[1000][3];
int dp[1000][3];


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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
            cin >> rgb[i][j];
    }

    // 첫 번째 집 칠하기
    dp[0][0] = rgb[0][0];
    dp[0][1] = rgb[0][1];
    dp[0][2] = rgb[0][2];

    // i번째 집에 j색을 칠하는 최소 비용의 합은 i-1번째 집까지 중 j색이 아니면서 비용이 가장 작은 경우를 택하면 됨
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (j == 0)
                dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + rgb[i][0];
            else if (j == 1)
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + rgb[i][1];
            else
                dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + rgb[i][2];
        }
    }
    
    cout << *min_element(dp[N - 1], dp[N - 1] + 2);
}


// 맞은 코드
// 출력 부분을 아래와 같이 고침
    int result = dp[N - 1][0];
    for (int i = 1; i < 3; i++)
    {
        if (result > dp[N - 1][i])
            result = dp[N - 1][i];
    }
    cout << result;

djm03178 2년 전 1

*min_element(dp[N-1], dp[N-1]+2) 으로 하면 dp[N-1][0], dp[N-1][1] 둘 중의 최솟값을 찾습니다. min_element의 둘째 인자는 그 위치는 제외하고 그 이전까지에서만 찾습니다.

bupjae 2년 전 1

52번째 줄에서 +2 가 아니라 +3 이 되어야 합니다.

stl 함수에 iterator 로 "범위"를 넘길 때에는, "시작점"은 자기 자신을 포함하며, "끝점"은 자기 자신을 포함하지 않습니다.

vector 같은 컨테이너의 begin(), end() 등도 같은 규칙으로,

begin() 은 시작 데이터를 가리키고 있고 (*begin() 으로 데이터를 얻을 수 있음),

end() 는 마지막 데이터 바로 다음 위치를 "가리키고" 있습니다 (*end() 는 절대로 하면 안 됨).

lisagamer 2년 전 0

이런 바보같은 실수를 했네요.. 감사합니다

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

문제

문제

출처

ICPC

출력부분에서 min_element를 썼더니 오답이 나옵니다 .

lisagamer 2년 전 0

djm03178 2년 전 1

bupjae 2년 전 1

lisagamer 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말