porque0525   4년 전

startAndLink 함수는 모든 player 중 절반을 선택해 조합을 구해 True, False로 나누는 함수이고

getAllCouple 함수는 먼저 True는 스타트 팀으로, False는 링크 팀으로 분배한 후에  능력치를  계산하는 함수입니다.

우선 강의처럼 go 함수 재귀를 두 번 하는 건 이해가 안되서 N/2만큼 조합을 구하는 방법을 썼는데

예제를 돌려 봤을 때 답은 맞게 나오는데 채점 시 시간 초과가 뜹니다.

제 접근 방법은 틀린 것인가요 ? ㅠㅠ 

pypy로 돌렸을 때는 맞았다고 나오긴 하는데 Python3으로 돌렸을 때 틀리다고 나와서 질문드립니다..!

djm03178   4년 전

시간 제한 자체가 원래 파이썬을 고려해서 만드는 경우가 별로 없고, 시간 보너스는 대략적으로만 매겨놓은 것이기 때문에 문제에 따라서는 매우 통과가 힘들거나 아예 불가능할 수도 있습니다. 파이썬이 느려서 그런 것일 뿐 어쩔 수 없습니다.

물론 더 효율적으로 만들어서 통과가 가능하게 만들 수도 있지만, 말 그대로 효율적인 풀이가 되는 것일 뿐 지금 코드가 틀렸다고 생각하는 건 애매한 것 같네요. 어쨌든 파이파이로는 통과시켰으니 그 정도면 충분하다고 봅니다.

djm03178   4년 전

참고로 파이썬은 C, C++에 비해 대략 30~100배 정도 느리다고 하는데, 시간 보너스는 *3 + 2초밖에 안 되니 이 문제에서도 총 4배밖에 안 됩니다.

wider93   4년 전

위 풀이와 본질적으로 완전히 같은 풀이를 한다고 가정했을 때 시간을 줄일 요소가 많이 있습니다.

일단 getAllCouple 함수에서 두 팀의 능력치를 구하는 방법이 이상합니다.

i != j인 i에 대해서 S[i][j]들을 더하는 것을 의도하셨을 텐데 더하는 값과 반복되는 값의 범위가 맞지 않습니다.

j<i인 경우에 대해 s[i][j]+s[j][i]를 다 더하거나, 모든 i, j에 대해 s[i][j]를 다 더해야 하는데 지금 범위는 애매하죠.

아마 값도 틀릴 수 있는 것 같은데 그 부분은 잘 모르겠고, 이것 때문에 계산이 2배 가까이 늘어납니다.


또 startAndLink 함수가 현재와 같을 경우 각 팀의 조합이 스타트 팀으로 한 번, 링크 팀으로 한 번 들어가서 불필요하게 두 번 계산하게 됩니다.

두 부분 수정하면 4배 정도 빨라져서 잘 통과하는 것 같네요.

porque0525   4년 전

좋은 답변 감사드립니다..!

i+1이 아닌 1이 들어가 있었군요. 말씀대로 하니 통과했습니다. 날카로운 지적 감사합니다.

그리고 startAndLink에서도 중복으로 뽑힌다는 것은 알고 있었는데 해결하는 방법으로 변수를 하나 추가한다는 것 외에는 생각이 나질 않더군요.

큰 시간 낭비는 아니겠지, 하고 간과하고 있었던 것 같습니다.

djm님께도 감사드립니다~! 참고하겠습니다!

wider93   4년 전

해결되었다니 다행입니다.

사실은 아래 부분을 매우 간단히 해결할 수 있는데, (0, 0) 대신에 (0, 1)을 주면 됩니다.(0이 언제나 링크 팀에 속하게 됩니다).

porque0525   4년 전

신기하군요...정말 그렇게 하니까 중복되지 않네요. 

혹시 왜 그렇게 되는지 여쭤봐도 될까요?

돌려보니 그렇게 된다는 것은 알겠는데, 제가 아직 알고리즘 사고가 부족한건지 그렇게 생각하게 되는 과정? 원리가 궁금합니다...ㅠㅠ

wider93   4년 전

startAndLink 에서 player[i]를 True로 마킹한다는 것은 start 팀에 i번 선수를 넣겠다는 것과 같은 뜻입니다.

(0, 1)을 호출한다는 것은 True로 마킹하는 범위에서 0을 제외하겠다는 것입니다. 

즉, "0번 선수가 들어간 팀을 항상 lTeam으로 부르겠다"는 말과 같게 됩니다. 물론 이는 일반성을 잃지 않고 딱 절반만 세 주겠지요.

porque0525   4년 전


그렇군요..이해가 됐습니다. 저도 언젠간 그런 아이디어를 생각해낼 수 있겠죠??

친절한 답변 감사드립니다~!!

kkjjh223   2년 전

오래된 댓글이지만 큰 도움이 돼서 댓을 남깁니다.

2번 반복되는 문제를 어떻게 해결할까 고민했는데 한쪽에 무조건 0번을 넣고 시작한다는 아이디어를 얻어서 python으로 제출하니

바로 통과했습니다. 감사합니다!

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