글 읽기 - 이 두 코드의 차이를 부탁드립니다!....

pmon2648 6년 전 0

제가 백준강의를 들으면서 문제를 풀어보고 있는데,

case1이 강의 핵심 코드고,

case2가 일단 코드를 안본체 강의만 보고 제가 짜본 핵심 코드입니다.

그런데 case1에서는 통과고 case2에서는 틀렸다고 나오는데

혹시 어떤 차이가 있어서 틀렸는지 고수분들께 부탁드려봅니다 ㅜㅠ

// d : 동적계획법 저장 배열
// a : 입력 데이터
// n : 입력 사이즈

// <case 1> 맞았습니다.
for (i = 0; i < s; i++) {
    d[i] = 1;
    for (j = 0; j < i; j++) {
        if (a[i] > a[j] && d[i] < d[j] + 1)
            d[i] = d[j] + 1;
    }
}


// <case 2> 틀렸습니다....
d[0] = 1;
for (i = 1; i < n; i++) {
    max = 0;
    for (j = 0; j < i; j++) {
        if (a[i] > a[j] && max < d[j]) {
            max = d[j];
            d[i] = d[j] + 1;
        }
    }
}

yukariko 6년 전 1

위 코드는 if (a[i] > a[j] && d[i] < d[j] + 1) 를 만족하지않아도 항상 d[i] >= 1 임이 보장되는데

아래코드는 그게 되고 있지 않네요. 즉, d[i] = 0 이 될 가능성이 있어 다른 값이 저장됩니다.

yukariko 6년 전 1

한가지 말씀드리자면 코드는 항상 풀코드를 올려주세요.

그렇지않으면 답변하는 사람들은 항상 눈으로만 디버깅을 해야합니다.

직접 돌려보면 훨씬 빨리 문제를 찾을수있는데도 말이죠.

pmon2648 6년 전 0

아 죄송합니다. 풀코드로 올리도록 하겠습니다!!

감사합니다!!

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

문제

문제

출처

ICPC

이 두 코드의 차이를 부탁드립니다!....

pmon2648 6년 전 0

yukariko 6년 전 1

yukariko 6년 전 1

pmon2648 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말