• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

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

22.02.17 03:13 작성 조회수 262

0

알고리즘 문제는 혼자 생각하고 해결하는 과정이 중요한 것을 알기에 정말 최대한 저혼자 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)

답변 2

·

답변을 작성해보세요.

0

북극곰님의 프로필

북극곰

2023.06.04

교수님께서 말씀하신대로 위 코드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

0

안녕하세요^^

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님의 프로필

sfdfs

2022.03.09

저도 조합으로 질문자님과 비슷하게 풀었는데, 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랑 비교하면 되지 않나요?