[2-5] 최대선호음식 시간초과..

import sys

N, D, K = map(int, input().split())
bits = [2 ** i for i in range(16)]
st = [0 for i in range(N)]
res = 0

def and_calc(a, b):
  if a & b == b:
    return 1
  return 0

def DFS(L, S, bit):
  global res
  
  if L == K:
    temp = 0
    for i in range(len(st)):
      temp += and_calc(bit, st[i])
    res = max(temp, res)
    return

  for i in range(S, D + 1):
    DFS(L + 1, i + 1, bit + bits[i])
  
  return

for i in range(N): # N
  input_value =  list(map(int, sys.stdin.readline().split()))
  
  for bit in range(len(input_value)):
    if bit == 0:
      continue
    st[i] += bits[input_value[bit] - 1]

DFS(0, 0, 0)
print(res)

영상과 유사하게 구현을 했는데도 시간 초과가 나서요..

어디가 문제인지 잘 모르겠습니다..

파이썬이라서 그런건지.. 😢

안녕하세요, 인프런 AI 인턴입니다. 사용자님께서 제공해주신 코드를 봤을 때 Python의 성능 문제가 있어 시간 초과가 발생할 수 있는 몇 가지 부분을 짚어볼 수 있습니다.

DFS 호출

K가 클 경우 DFS의 깊이가 깊어지면서 시간 복잡도가 기하급수적으로 증가합니다. K와 D의 값에 따라 시간 초과가 발생할 수 있습니다.

비트 연산 최적화

Python에서 비트 연산이 C++에 비해 상대적으로 느릴 수 있습니다. 하지만, 이 문제는 비트 연산 자체보다는 DFS에서 중복된 상태를 방문하는 것이 더 큰 문제일 가능성이 높습니다.

입력 처리 속도

sys.stdin.readline()을 사용하셨는데, 이는 이미 입력 받는데 걸리는 시간을 최소화하는 방법입니다.

해결 방법으로는 다음을 고려해보실 수 있습니다:

알고리즘 개선

백트래킹을 사용하여 필요 없는 상태는 빠르게 배제하고 DFS를 더 빠르게 하도록 할 수 있습니다.

불필요한 연산 제거

반복문 내에서 불필요한 연산이 없는지 점검해보세요. 예를 들어, and_calc 함수 내부에서 return 1이나 return 0 대신 bool 타입을 직접 반환하는 것이 약간의 성능 향상을 가져올 수 있습니다.

더 빠른 언어 사용

Python이 C++에 비해 속도가 느린 것은 사실입니다. 시간이 중요한 문제에서는 C++과 같은 성능이 더 뛰어난 언어를 고려해볼 수도 있습니다.

위의 내용을 참고하여 코드의 성능을 개선해보시길 바랍니다. 추가적으로 도움이 필요하시면 인프런 Q&A나 커뮤니티 포럼을 통해 도움을 요청해보세요.

인프런 커뮤니티 질문&답변