백준 1890번 점프 문제입니다. 이게 대체 왜 틀린 코드인 건지 모르겠어요 ㅠㅠ 반례 좀 찾아주세요반례 찾는 사이트도 이용해봤는데 안 나오네요 ㅠㅠ#include using namespace std;int main() {int mem[110][110] = { 0 };int scale;cin >> scale;//게임판 입력int jump_game[100][100] = { 0 };for (int j = 0; j < scale; j++) {for (int k = 0; k > jump_game[j][k];}}//기저사례 입력mem[scale - 1][scale - 1] = 1;//0,0까지 확인하기for (int y = scale - 1; y >= 0; y--) {for (int x = scale - 1; x >= 0; x--) {if (x == scale - 1 && y == scale - 1) continue;mem[y][x] = mem[y + jump_game[y][x]][x] + mem[y][x + jump_game[y][x]];}}//결과출력cout << mem[0][0]; return 0;}
안녕하세요
코드를 꼼꼼히 봤는데, 아주 미묘한 논리 오류가 있습니다. 틀린 이유와 반례, 그리고 왜 안 나오는지까지 설명드릴게요.
1. 코드의 핵심 문제점
아래 부분이 문제입니다:
mem[y][x] = mem[y + jump_game[y][x]][x] + mem[y][x + jump_game[y][x]];
여기서 jump_game[y][x]가 0일 때,
mem[y][x] = mem[y][x] + mem[y][x]; 즉, mem[y][x] = 2 * mem[y][x];가 됩니다.
이게 의미상 오류가 아니라, 이동 불가능(0은 점프 X)이면 그 칸에서 시작해서 도착점에 도달하는 경우는 0이 되어야 합니다.
그런데, 위 코드에서는 0일 때도 mem 배열을 건드려버립니다.
또한, 배열 인덱스 범위 체크를 하지 않아 out of bounds 접근이 생길 수 있습니다. (BOJ에서는 디폴트 0으로 초기화라 런타임 에러는 잘 안나오지만, 논리적으론 잘못입니다.)
2. 대표 반례
반례 예시:
3
2 0 0
0 0 0
0 0 0
이 경우, (0,0)에서 오른쪽이나 아래로 이동 자체가 불가능합니다.
정답은 0이 나와야 합니다.
당신 코드에서는,
(0,0)에서 jump값이 2 → mem[2][0]과 mem[0][2]를 더하게 됨
그런데 둘 다 0이어야 정상이나, 인덱스 범위 벗어나서 디폴트로 0이긴 합니다.
하지만 만약 (0,0) jump값이 0이면 자기 자신을 2배로 하게 되어버립니다(논리 오류).
3. 실제로 오답이 나오는 반례
좀 더 일반적인 예시:
4
2 0 0 0
0 2 0 0
0 0 2 0
0 0 0 0
정답: 0
(이동이 불가)
4. 진짜 "틀린 답"을 뱉는 반례 (0 점프 시 문제)
예시:
2
0 0
0 0
정답: 0이어야 하지만, 코드에 따라 이상한 값(무한 루프 또는 자기 자신 2배)이 될 수 있습니다.
5. 올바른 코드 조건
jump 값이 0이면 해당 칸은 처리하지 않고 넘어가야 함.
배열 범위 체크 필수!
6. 수정 예시
아래처럼 고치면 됩니다.
#include <iostream>
using namespace std;
int mem[110][110];
int jump_game[110][110];
int main() {
int scale;
cin >> scale;
for (int i = 0; i < scale; i++)
for (int j = 0; j < scale; j++)
cin >> jump_game[i][j];
mem[scale-1][scale-1] = 1;
for (int y = scale-1; y >= 0; y--) {
for (int x = scale-1; x >= 0; x--) {
if (x == scale-1 && y == scale-1) continue;
if (jump_game[y][x] == 0) continue; // ★ 이 줄 추가!
int jump = jump_game[y][x];
if (y + jump < scale) mem[y][x] += mem[y + jump][x];
if (x + jump < scale) mem[y][x] += mem[y][x + jump];
}
}
cout << mem[0][0];
return 0;
}
핵심:
jump_game[y][x] == 0이면 continue;
배열 범위 체크
7. 반례 사이트가 못 잡는 이유
BOJ 같은 곳에선 일부러 "0" 점프가 없는 예시만 넣기도 해서 그렇고,
단순한 코드 구조로 인해 인덱스 에러는 안 나지만, 논리적으로 "틀린 답"이 나올 수 있습니다.
-----------------------------
끝으로 전문가 중개플랫폼에서 Python, C // 알고리즘, 과제, 데이터분석, 모든 라이브러리 관련
도움드리고 있습니다. 상담받으실일있으시면 참고 부탁드립니다.
>C, 파이썬, 알고리즘 과제관련 상담(PC접속시 링크)
참아야지! 참아라! 그러면 잘 되어 갈 걸세. 친구여, 정말 자네 말이 맞네. 세상 사람들 틈에 끼여 날마다 일에 쫓기며, 다른 사람들이 하는 일과 그들의 행동을 보기 시작한 이후로 나는 나 지신과 휠씬 더 잘 타협할 수 있게 되었네. 젊은 베르테르의 슬픔 - 괴테