aiden3233   11달 전

틀린부분 지적까진 바라지 않으니 반례 몇개만  찾아주실수 있나요?

sinderella   11달 전

동적 프로그래밍(DP) 캐싱의 문제점:

dp[505][505][505] 배열을 사용하여 cm 함수의 결과를 캐싱합니다. 

초기값은 모두 0입니다.

if(dp[x][y][z]) return dp[x][y][z]; 

이 코드는 dp[x][y][z] 값이 0일 경우, 캐싱된 값이 없다고 판단하고 다시 계산합니다.

문제: 만약 cm 함수가 계산 결과로 유효한 값 0을 반환할 수 있다면, 이 조건문은 항상 false가 되어 중복 계산이 발생합니다. 

이는 DP의 목적에 어긋나며, 심한 경우 시간 초과를 유발할 수 있습니다.

해결책: 캐싱 여부를 확인할 별도의 visited 배열을 사용하거나, 반환 값에 1을 더해서 저장하는 등(저장 시 +1, 반환 시 -1)의 방법으로 0과 '계산 안 됨' 상태를 구분해야 합니다.

도움이 되면 좋겠네요!

aiden3233   11달 전

cm 함수는 x=y=z=0 이 아니면 0을 반환할 일이 없을거 같아요.. 그리고 시간초과는 안나서 다른 부분 문제인거 같아요.

alreadysolved   11달 전

7
6712345
5671234
4567123
3456712
2345671
1234567
7123456

위 예제입력에서 6이 아니라 7을 출력합니다.

7*A = 0이 되는 케이스를 처리 못하는 문제 같습니다.

https://testcase.ac/problems/1...에 추가해놨으니 추가반례 찾으실 수 있을겁니다.

aiden3233   11달 전

그러네요! 감사합니다!

sinderella   11달 전

5

1

12

123

1234

12345

4
1111111
2222222
3333333
4444444

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