이코드는 무엇이 잘못된것인가요?

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

2. 휴가(DFS)

작성

340

알고리즘 문제는 혼자 생각하고 해결하는 과정이 중요한 것을 알기에 정말 최대한 저혼자 2시간동안 디버깅을 해보았지만 무엇이 잘못된 것인지 모르겠어서 질문 남깁니다.

조합만들기 식으로 풀어봤는데 제가 생각하기에 논리상으로는 맞는것 같은데 계속 답이 이상하게 나옵니다.

한번만 코드 검토 부탁드립니다...

import sys
sys.stdin=open("input.txt","rt")

def DFS(v, money):
   global maxMoney
   if maxMoney<money:
      maxMoney=money
   if v>n:
      return
   for i in range(v,n+1):
      DFS(v+sch[i][0], money+sch[i][1])

if __name__=='__main__':
   n = int(input())
   ch=[0]*(n+1)
   sch=[(-1,-1)]
   maxMoney=-1
   for _ in range(n):
      # t는 걸리는 시간(일), p 는 보수
      t, p = map(int,input().split())
      sch.append((t,p))
   DFS(1,0)
   print(maxMoney)

python 코테 준비 같이 해요!

답변 2

북극곰

교수님께서 말씀하신대로 위 코드v+sch[i][0]처럼 했을 경우에 v와 i값이 달라질수 있어 이상한 값이 누적될 수 있습니다. 예를 들어 v=1인데 i가 2인 경우, 1일차임에도 2일차 상담을 했을때의 소요시간이 더해져 값이 달라지게 됩니다. 따라서 i+sch[i][0]으로 수정해야될거같네요.

또한 저 코드 기준으로 v>n일때 return을 해주고있는데 위 예시처럼 7일차 상담이 1일이 걸리는 경우도 가능하므로 v>n+1일때 return을 해주어야할거같습니다. 이렇게 수정을 해서 코드를 작성하니깐 정답이 나오는거 같네요.

정답코드.png

김태원

지식공유자

안녕하세요^^

DFS의 매개변수로 사용하는 v의 값을

for i in range(v, n+1):

DFS(v+sch[i]][0], money+sch[i][1])

상담예약을 접근하는 인덱스번호로 사용하는데 다음 재귀함수의 v값으로 넘기는 값은 v+sch[i][0]값을 더하는게 좀 이상하네요. sch[i][0]값은 i번째 상담을 하는데 걸리는 시간인데요.

sfdfs

저도 조합으로 질문자님과 비슷하게 풀었는데, v가 1일이라고 하면 v+sch[i][0]은 1일에 4를 더해서 5일로 가는게 맞지 않나요? 그럼 또 v=5 에서 v+sch[i][0]은 5+2이니까 7일이 되구요. 그다음 v=7에서 v+sch[i][0]은 7+1이니까 8일이 돼서 여기서 중지하고 수익을 max랑 비교하면 되지 않나요?

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

이코드는 무엇이 잘못된것인가요?