knight7024   2년 전

TLE를 받은 소스 : https://www.acmicpc.net/source...

AC를 받은 소스 : https://www.acmicpc.net/source...

두 개의 차이는 dp값을 변수에 저장해놨다가 비교하는 것 뿐인데 왜 그렇게 큰 차이가 나는지 궁금합니다.

이상하게 TLE가 계속 나서 다른 분들의 소스를 보니 다들 이런 방식을 사용하시더군요.

knight7024   2년 전

아앗 주소를 변경했었는데 글 수정이 제대로 안되어 있었네요 ㅠㅠ 수정했습니다!

knight7024   2년 전

배열 값을 불러오는 횟수도 생각해야 하는 건가요? 많이 호출해도 무리 없을 줄 알았는데 그게 아니었군요...

djm03178   2년 전

dp를 할 때와 안 할 때의 차이를 쉽게 느낄 수 있는 예시 중에 피보나치 수를 재귀로 구하는 것이 있습니다.

knight7024   2년 전

제가 지금보니 글을 애매하게 쓴 듯 하네요

1. if (visited[y][x] != -1) return visited[y][x]; int ans = 0;

2. int &ans = visited[y][x]; if (ans != -1) return ans; ans = 0;

이 둘의 차이가 궁금했습니다. 1번은 TLE이고 2번은 AC입니다.

djm03178   2년 전

시간 초과가 나는 코드 어디에도 visited 값을 초기 상태 이후로 갱신해주는 곳이 없습니다. 그러니 당연히 dp를 전혀 안 한 것이나 다름이 없죠.

knight7024   2년 전

아 &ans를 통해 visited[0][0]부터 갱신해주는 거지요? 설명을 듣고나니 알거 같습니다..

djm03178   2년 전

int &ans = visited[y][x]; 에서 &가 하는 역할이 뭔지 아시나요? 시간 초과 코드는 &가 없기 때문에 문제가 되는 겁니다.

knight7024   2년 전

변수를 공유하는거 아닌가요? 별명 같은거라고 들었습니다.

djm03178   2년 전

네 그렇죠. 참조자라고 불리는데, 정답을 받은 코드에서는 int &ans = visited[y][x]; 를 통해 ans가 곧 visited[y][x] 대용으로 쓰이고 있고, 그래서 ans에 값을 대입하고 변경하는 건 곧 visited[y][x]의 값을 변경하는 것과 같습니다. 그래서 dp가 되는 거죠.

하지만 시간 초과를 받는 코드에서는 visited는 처음에 -1인지 여부를 볼 뿐이지, 답을 구하는 과정에 전혀 연계되어 있지 않습니다. 임시 변수 ans를 선언한 뒤, 계산을 여기에 하고 반환하고 나면 사라져버리는 거죠.

knight7024   2년 전

늦은 시간까지 상세한 답 감사합니다. 풀이를 다 생각해놓고 정작 부족하게 코딩했네요.

큐브러버님도 답변해주셔서 감사합니다. 질문글을 확실하게 못써서 죄송합니다 ㅠㅠ

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