cedar09212   6년 전

칼로리, 가격 인덱스가 5000

dp 인덱스가 10000이면 틀렸습니다 나오고


칼로리, 가격 인덱스가 5001

dp 인덱스가 10001이면 맞았습니다 라고 나오는 이유가 무엇인지 궁금합니다.


런타임에로도 아니고 틀렸습니다..라는게 이해가 안가기도 하고요..

문제에 n과 m의 범위가 명시되어있는데 인덱스를 1개더 잡아줘야된다는 것도 잘 모르겠습니다.


jwvg0425   6년 전

각각 인덱스들이 다 5000, 10000까지 갈 수 있으니까 배열을 5001개, 10001개 잡아줘야 하구요(인덱스는 0부터 세니까 5000,10000개면 0~4999, 0~9999로 자리가 하나씩 모자라죠), 런타임 에러가 아니라 틀린 답이 나오는 이유는 C/C++에서 배열 메모리 참조 연산([])은 단순히 시작 주소로부터 해당 숫자만큼 건너뛴 위치의 값을 참조하는 방식으로 동작하기 때문입니다.


 지역변수에 저렇게 배열, 변수들을 선언하면 스택에 해당 변수들이 저장될 위치가 순서대로 확보가 되는데요(항상 그렇다고 말할 순 없지만 대개 그렇다고 보시면 됩니다). 그 결과 대충 말하자면 int c[5000]; int p[5000];이 순서대로 선언된 상태에서 c[5000]을 참조하면 c[4999]까지가 c의 범위고 그 뒷자리에 바로 p를 위한 저장 공간이 할당되기 때문에 실질적으로 c[5000] = p[0]과 같은 의미가 되어버립니다. 마찬가지로 p[5000] = dp[0], dp[10000] = 그 뒤에 선언 된 지역 변수의 위치, 예를 들면 i나 ans 등을 가리키게 될 수 있습니다. 이런 식으로 됐을 경우 해당 메모리 위치가 건드리면 안 되는 위치를 건드린 건 아니기 때문에 런타임 에러가 나진 않지만, 엉뚱한 값을 수정했으니 틀린 답이 나오게 되지요.

cedar09212   6년 전

인덱스는 정말 단순한건데 제가 생각을 못햇네요..;;


나머지 설명은 친절하게 답변해주셔서 감사합니다. 도움이 많이 되었습니다.

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