nzzangyh   2년 전

미친놈처럼 3일동안 이문제만풀려고 10시간은 투자한거같은데,,

자괴감만 들고 있습니다...

구글링을 통해, 어떻게 풀면 시간초과안나는 모범답안 이겠구나라는 발상을 얻긴 했습니다만,

제 코드를 구제할수 없을까? 라는 욕심에 계속 매달렸는데 도저히 못하겠습니다..


제코드의 어떤 수정이 있어야지

c++언어로 시간초과를 벗어날 수 있을지 간절히 알고 싶습니다. 


한분이 글로 올려주신, 밑에 내용이 제 코드에서 check_ladder, ladder라는 함수의 경우인데요,,

이것을 어떻게 어느시작점이  어느끝점으로 가는지에 대해 저장을할수있을지에 대한 아이디어도 생각이 안나서, 고견도 듣고싶습니다..

//시간 초과가 난다면 원인은 딱 하나입니다.

//사다리를 다 놓고 나서야 "i번 세로선의 결과가 i번이 나와야 한다"를 직접 시뮬레이션을 돌려서 확인하는 것은 매우 비효율적입니다.

//사다리를 하나 놓을 때마다 어느 시작점이 어느 끝점으로 가는지 저장해 두면 시뮬레이션을 안 돌리고 바로 확인할 수 있습니다.

cesta123   2년 전

check_ladder 부분에서 state=0일때는 되자마자 return false; 바로 해버리는 건 어떨까요? 저 또한 비슷한 방식이었어서 말씀드리자면..
문제 테스트케이스 맞으시고, 9%에서 멈추신거면, 아마 2초에 간당간당 하실거 같고, 그거만 넘기시면 아마 통과하실거라고 생각들어요. 시간초과가 나기 쉬울수 밖에 없는 것이 1개때 놓았던 곳을 3개 놓을 때 또 다시  중복적으로 놓고 있어서 그렇더라구요.
다른 한가지는 저 같은 경우 왼쪽에 1, 오른쪽에 2로 하지 않았고, 그냥 사다리를 1로 본다음 j-1에 1이있으면, j입장에서 왼쪽에 연결 되어있으니까 j-1로 가고, j에 1이 있으면 오른쪽으로 가라는 식으로 했었어요. 별 차이가 없어보였지만 제가 처음에 짠 코드에서 1. a[i][j] =1; a[i][j+1]=2;로 구현했을 때와 2.  a[i][j]=1;로만 놓고 if(a[i][j-1] == 1) j-=1; else if(a[i][j] == 1) j+=1; 로 했을때전자는 시간초과났고 후자는 간당간당하게 통과했습니다. 엄청 빠르게 하려면 뜯어 고쳐야하지만 최대한 안 고치는 선에서 말씀드립니다. 도움이 되셨다면 한번 실행해보세요~!

cesta123   2년 전

아 그리고 후자 방식으로 해보실거면, 처음에 초기화 부분에서 v[a-1][b] = 2;이거 빼시고 하셔야 합니다. 고칠 때 처음에 빼는거 깜빡하고 안됐어서 당황했었거든요

nzzangyh   2년 전

댓글 고맙습니다. 답변자님의 이 문제에 대한 채점현황을 보니, 저와같이 고생하셨다는 것이 느껴지네요,,,

나중에 말씀해주신 부분으로 꼭 참고해서 통과해보겠습니다.

내일 좋은결과있으시길!

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