글 읽기 - 정말 괴상한 것을 발견했습니다. 진짜 신기해요

hellowfriend 1년 전 1

dp를 갱신하는 for 문을

i = 0부터 시작하면

arr[-1][0]을 이용하게 되서

for문을 i = 1, j = 0부터 시작하게 했는데 틀렸습니다. 라고 떠서

그냥 이 for문을 i도 0부터 시작하게 했는데 맞았습니다.라고 떴습니다.

그런데 maxValue선언을 main 함수 바깥으로 보내니 또 갑자기 틀렸습니다. 떴습니다.

도저히 왜 그런지 모르겠어서 질문을 드립니다.

아시는 분이 있으시다면 알려주시면 감사하겠습니다.

좋은 하루 보내세요!

#include <iostream>

using namespace std;

int arr[500][500] = {};

int main(){
    int N, maxValue = 0;    //
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0 ; j <= i; j++){
            cin>> arr[i][j];
        }
    }
    
    

    for(int i = 1; i <N ; i++){    //여기서 i를 0으로 바꾸면 맞았습니다.가 뜨고 이렇게 바꾼 후 maxValue선언을 main함수 바깥으로 꺼내면 또 갑자기 틀렸습니다. 가 뜹니다.
        for(int j = 0; j <= i; j++){
            if(j == 0) {
                arr[i][j] = arr[i-1][0] + arr[i][0];
            }else if(j == i){
                arr[i][j] = arr[i-1][j - 1] + arr[i][j];
            }else {
                arr[i][j] = max(arr[i-1][j], arr[i-1][j-1]) + arr[i][j];
            }
            if(i == N - 1) maxValue = max(maxValue, arr[i][j]);
        }
    }
    cout << maxValue << "\n";

}

kokosoko59 1년 전 0

정말 모르겠네요 i=1 이 맞는 코드 같은데요

hellowfriend 1년 전 1

하나 알아냈습니다. i=1일 때 maxValue 갱신이 안되네요.

이제 i를 0부터 시작하도록 바꿨을 때

왜 arr[-1][0]이 작동하는 지랑

이렇게 바꾼 후 maxValue를 main함수 바깥으로 꺼내면 왜 또 틀리는 지 궁금합니다.

adung7 1년 전 2

저도 마침 알아내고 댓글을 달려고 했는데 그 부분을 제외하면 음수 인덱스 접근이 왜 답이 되었는지랑 maxvalue를 함수 바깥으로 꺼냈을 때 틀리는 현상에 대해 알려드리자면

그 부분은 c++의 Undefined Behavior 줄여서 보통 UB라고 말하는 것 때문입니다 정의되지 않은 접근이고 이 접근이 무슨 값이 되는지는 알 수가 없습니다

따라서 음수 인덱스 접근을 했을때 운이 좋아서 0이 나왔다던가 하는 상황이 발생할 수 있고 따라서 정답을 맞은 것으로 보입니다 그때는 어쨌든 maxvalue값이 갱신이 됐을테니까요

마찬가지의 이유로 maxValue를 바깥으로 옮겨서 왜 틀렸느냐 하면 그것도 단순히 운입니다 음수 인덱스 접근을 했을것이고 이 값에 따라 쓰레기값이 들어있었으면 답이 될수 없던것이지요

hellowfriend 1년 전 0

maxValue 선언이 main함수 바깥으로 나가면서 이 코드에서 원래 운으로 0이 나오던 음수 인덱스값에 어떻게든 영향을 미치게 된거군요?

adung7 1년 전 0

네 그러한 것으로 보입니다 arr배열 전에 선언했다면 arr[-1][0]이 maxValue로 잡혔을 수도 있습니다

hellowfriend 1년 전 0

오 확인해보고 싶어서 저기서 i = 0부터 시작하도록 한 후 이번에는 int n을 바깥으로 보내니까 역시 틀렸다고 뜨네요! 설명 감사합니다!

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