c3171700   6년 전

안녕하세요 고수님들..

일단 직관적으로 풀고 제출 했는데 시간초과가 나왔네요..

제 코드 주석 상 "1. 번호 + 직접가는것" 의 감소 / 증가 순서대로 찾아서 비교하는 부분에서 다소 시간이 많이 걸린 것 같은데,

시간초과가 될 만한 케이스와, 좀 더 나은 방안 혹은 정확히 시간초과가 나게 된 원인 정도라도 조언을 구할 수 있을까요 ?

dreamian   6년 전

ispossible 함수가 모호합니다.

101 10

0 1 2 3 4 5 6 7 8 9를 입력할 때

무한 루프를 도는 것을 볼 수 있습니다.

모든 버튼이 고장났기 때문에 이런 경우에는 43번째 while문에서 빠져나올 수 없게 됩니다.


또한, 감소하는 경우에도 문제가 있습니다.

문제에 제시된 조건을 만족하는 N에 대해 아래의 입력을 받는 경우에,

N 10

0 1 2 3 4 5 6 7 8 9

34번째 while문 수행 중에, ispossible함수는 temp값이 결국 0이 되어 5번째 while문을 빠져나와 false를 리턴해야 하는데 true를 리턴합니다.

43번째 while문은 주어진 값이 계속 올라갈 수 밖에 없으므로 무한 루프를 돕니다.


이 문제의 경우에는 이런 저런 조건을 다 따지는 것보다 브루트 포스를 이용해서 해결하는 게 효율적이라 생각합니다.


가고자 하는 채널을 N이라고 할 때, N~최대 채널의 경우까지 갈 수 있는 경우와 0~N까지 갈 수 있는 경우 중에 최소한의 버튼을 누르는 경우를 생각하면

0ms로 해결할 수 있습니다.


도움이 되셨으면 좋겠습니다.

c3171700   6년 전

@dreamian 님 감사합니다 !!

말씀주신 것을 바탕으로 고쳤다가, 두 번이나 더 틀려서 반례를 못찾다가

1

9

1 2 3 4 5 6 7 8 9

케이스 처리 안한것을 이제야 보고...AC 받았습니다 ㅠㅠ 감사합니다 

Screen Shot 2018-01-16 at 1.09.52 AM.png

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