강의로 돌아가기
김세윤

C++로 풀어도 반복문 두번돌리면 안될정도로 시간제한 빡빡하나요?

N이 백만밖에 안되는데 반복문 두번돌리면 시간초과나네요

1번만 돌리게 짜려면 코드가 좀 더러워지긴 해도 맞출수는 있을거 같긴한데 그걸 한다고 딱히 실력이 늘진 않을거같고 걍 노가다라서 망설여지는데.. 이 문제 C++로 풀어도 원래 반복문 한번밖에 허용 안할정도로 제한 빡빡하나요?

1 개의 답변
이도원

반복문 2번 돌린다는게 시간복잡도 n2 으로 푼다는건가요? n2 으로 풀어보진 않아서 모르겠고, 시간복잡도 n으로 하니까 효율성테스트 통과하네요. 그리고 잘 모르긴하는데, C++이든 java든 그 언어에 맞게 시간계산하지 않나요?

  • 김세윤
    복잡도는 n 인데 이걸 두번해서 2n이 되니까(n^2 아니고 2n) 시간초과 나네요. 2n일때는 정확도는 다 맞는데 효율성 전부 시간초과나고, n일때는 효율성에서도 정답뜨긴 하는데 한두개씩 틀렸다고 뜹니다. 노가다하면 맞출수는 있을거 같긴한데... 이게 의도된거라면 너무 빡빡한거같아서;; 김세윤 2019.02.25 17:52
  • 이도원
    저도 시간복잡도 2n인데 효율성 통과했어요. 반복문 안에 있는 코드를 수정하면 될 것 같네요. 이도원 2019.02.25 19:25
  • 김세윤
    넵 한번해보겠습니다 김세윤 2019.02.26 23:39
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.