1단계 더 호출하기 전에.
부호가 맞는지 검사하는 건 어떨까요? 그 상태로는 20^10이라 시간초과 나는 건 당연할 거 같아요.
조금 더 opt를 시키시려면.. 0인 것은 어짜피 답이 정해져 있으니까.
[i,i]까지 합이 +고, [i+1,i+1]까지 합이 -. 이렇게 부호가 바뀐다고 해 봅시다. 그럴 때
[i,i+1]까지 합이 어떤 부호를 가지느냐에 따라서, 답이 될 수 있는 범위가 정해질 겁니다. 예를 들어 [i,i+1]의 합이 +라면
|ans[i]| > |ans[i+1]|일 겁니다. 전체 100가지 경우에서 45가지 경우로 줄어버리죠.
이런 식으로 부호가 바뀌는 부분에 대해서 좁혀나가시면.. 되리라 생각합니다.
scared22 5년 전
-10 부터 10까지 n이 될 때까지 tmp배열에 대입하여
미리 입력한 부호가 맞는지 확인하여 맞으면 출력하고 끝내는 방식으로 구현했습니다.
TL을 피할 수 있는 방법이 없을까요 ㅜㅜ
가르쳐주시면 감사하겠습니다.