qqwq9999   2년 전

정답률 50프로 정도에서 틀렸습니다가 발생합니다..

1697번 틀렸습니다 질문글을 4페이지까지 뒤져보고 반례를 전부 적용했을 때는 답이 올바르게 나왔습니다 ㅜㅜ


제 코드의 경우 반례가 어떤게 있을까요..?

greedev   2년 전

compile online에서 돌려봤을때

100000 0 넣으면 작동 안되던데

한번 해보시면...

djm03178   2년 전

visited가 초기화되지 않았습니다.

djm03178   2년 전

그건 dep>dst인 경우에 대한 예외 처리를 했을 뿐이고, 나머지 부분은 동작이 어떻게 될지 알 수 없습니다.

greedev   2년 전

50프로 정도에서 틀렸다면 초기화 문제는 아닐 것 같네요

greedev   2년 전

그리고 예외를 처리하니 맞았습니다...

djm03178   2년 전

문제가 아닐 것 같다고 하지 말고, 초기화가 되지 않았는데 동작이 잘 되느냐는 그냥 운입니다. 0이라는 값은 메모리 상에 빈도가 극도로 높으니, 운 좋게 통과되는 것도 무리가 아니죠. 똑같은 환경이라면 여러 번 반복해도 같은 결과를 낼 가능성도 매우 높습니다.

greedev   2년 전

아 그럴수도 있겠군요;;;

그런데 혹시 c++과 c++14 차이점 아시나요?

아래 소스는 c++14에서 돌아가는것 같긴 한데...

djm03178   2년 전

좀 더 확률론적인 이야기를 하자면, 작은 좌표에서 큰 좌표로 이동하는 건 대체로 적은 이동 횟수로도 도달이 가능하므로 비교적 적은 수의 좌표들의 visited만 "운 좋게 0"이었으면 됩니다. 하지만 역으로 위에서 내려올 때는 그 사이에 있는 모든 좌표를 다 방문해야 하므로 단 하나라도 0이 아닌 게 있었다면 정답을 찾을 수가 없습니다.

이 코드에서 visited만 0으로 초기화하고 시작해도 맞습니다. 굳이 예외 처리를 할 필요가 없이, 어떤 환경이라도 항상 올바른 알고리즘을 만들 수 있는데, 굳이 나머지는 운에 맡기고 특수 상화에 대한 예외 처리만 할 필요는 없죠.

greedev   2년 전

그렇군요...

저의 짧은 생각과는 다르게 매우 대단하십니다...센세...

qqwq9999   2년 전

두 분 다 답변 감사합니다. 로직에 대해 정확한 이해없이 작성하다보니 초기화도 잊었네요. 댓글 감사합니다.

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