• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

시간초과 관련

22.08.19 15:02 작성 조회수 212

1

안녕하세요. 자바로 풀다가 파이썬으로도 풀어보고 싶어서 해당 문제를 동일 로직으로 작성했는데, 예시 3, 4번에서 시간초과가 발생했습니다.(자바 코테 강의지만 파이썬 관련 질문을 드려서 죄송합니다. ㅠㅠ)
 
해결하는 로직은 동일하니 수단만 바뀌었다고 생각했었는데 파이썬의 한계를 느껴보니 다시 자바로 돌아가야하나..하는 생각이 들었습니다. 이렇게 언어로 인해 정답 오답이 결정되는 케이스가 많을까요?
 
(참고로 다른 설명을 보니 백트래킹 조건에 sum > c 조건에 추가 조건을 통해 시간을 줄일 수 있는 방법을 알았습니다. 다만 자바에서는 해당 조건 없이도 통과가 되니 추가 조건을 고려해야 한다는 단점을 느꼈네요 ㅠ)
import sys


def DFS(L, subTotal):
    global maximum
    if subTotal > c:
        return
    if L == n:
        maximum = max(maximum, subTotal)
    else:
        DFS(L + 1, subTotal + a[L])
        DFS(L + 1, subTotal)

c, n = map(int, sys.stdin.readline().split())
a = []
for _ in range(n):
    a.append(int(sys.stdin.readline()))
maximum = 0
DFS(0, 0)
print(maximum)

답변 1

답변을 작성해보세요.

1

안녕하세요^^

파이썬이 자바보다는 처리속도가 확실히 느립니다. 

대부분 테스트 언어로 파이썬을 허용할 경우 시간제한을 자바보다 더 주는 경우가 많습니다. 즉 자바는 1초에 처해야 한다면 파이썬은 3초 정도로 여유있게 줍니다. 언어는 본인이 편한 언어로 해도 상관없습니다.

leejohy님의 프로필

leejohy

질문자

2022.08.20

많이 고민했는데 빠르게 답변해주셔서 감사드립니다..!!!!