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; 로 했을때전자는 시간초과났고 후자는 간당간당하게 통과했습니다. 엄청 빠르게 하려면 뜯어 고쳐야하지만 최대한 안 고치는 선에서 말씀드립니다. 도움이 되셨다면 한번 실행해보세요~!
nzzangyh 2년 전
미친놈처럼 3일동안 이문제만풀려고 10시간은 투자한거같은데,,
자괴감만 들고 있습니다...
구글링을 통해, 어떻게 풀면 시간초과안나는 모범답안 이겠구나라는 발상을 얻긴 했습니다만,
제 코드를 구제할수 없을까? 라는 욕심에 계속 매달렸는데 도저히 못하겠습니다..
제코드의 어떤 수정이 있어야지
c++언어로 시간초과를 벗어날 수 있을지 간절히 알고 싶습니다.
한분이 글로 올려주신, 밑에 내용이 제 코드에서 check_ladder, ladder라는 함수의 경우인데요,,
이것을 어떻게 어느시작점이 어느끝점으로 가는지에 대해 저장을할수있을지에 대한 아이디어도 생각이 안나서, 고견도 듣고싶습니다..
//시간 초과가 난다면 원인은 딱 하나입니다.
//사다리를 다 놓고 나서야 "i번 세로선의 결과가 i번이 나와야 한다"를 직접 시뮬레이션을 돌려서 확인하는 것은 매우 비효율적입니다.
//사다리를 하나 놓을 때마다 어느 시작점이 어느 끝점으로 가는지 저장해 두면 시뮬레이션을 안 돌리고 바로 확인할 수 있습니다.