-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
뭐가 틀린것인지 잘 모르겠습니다
24.03.01 16:36 작성 조회수 85
0
n , m = map(int,input().split())
lst=[list(map(int,input().split())) for _ in range(n)]
dy=[0]*(m+1)
ch=[[] for _ in range(m+1)]
for i in range(n):
for j in range(lst[i][1],m+1):
if dy[j] < dy[j-lst[i][1]]+lst[i][0] and (i not in ch[j-lst[i][1]]):
ch[j]=ch[j-lst[i][1]] + [i]
dy[j] =dy[j-lst[i][1]]+lst[i][0]
print(max(dy))제가 짠 코드는 원래값이랑 리스트돌면서 이 시간만큼썼을때 더해지는 점수랑 비교해서큰값으로 바꿔주는것입니다.만약 리스트돌면서 이 시간만큼썼을때 더해지는 점수가 컸을때는 해당하는 문제를 푼것이 되니깐 ch에 그 index가 있는지 없는지를 비교해서 있으면은 안바꿔주고 없으면은 바꿔주는것입니다.
만약에 없어서 바꿔주면은 ch에 그 index를 추가하는 방식으로 구현을했는데 왜 틀린것인지 모르겠습니다
답변을 작성해보세요.
0
인프런 AI 인턴
2024.03.03
안녕하세요, 인프런 AI 인턴입니다.
wwweric12님, 파이썬으로 알고리즘 문제풀이 시 코드에 문제가 있어 답답하셨을 것 같아요. 제공해 주신 코드를 보니, 동적 계획법(Dynamic Programming)을 사용하여 풀이하려는 접근 방식을 확인할 수 있습니다. 각 문제를 해결하며 얻을 수 있는 점수(dy 리스트)와 해당 문제를 풀었는지 여부를 표시하는 행동 기록(ch 리스트)을 잘 구현하셨네요.
코드에서 잘못된 부분을 찾기는 힘들지만, 몇 가지 수정해 볼 수 있는 부분을 제안드리겠습니다:
조건문
(i not in ch[j-lst[i][1]])에서i문제가 이전에 풀려 있는지 확인하는 것이 좋아 보이나, 알고리즘의 전반적인 로직을 검토할 필요가 있어 보입니다. 목표는 중복된 문제를 풀지 않게 하는 것인데, 이 로직이 의도대로 작동하는지 확인해주세요.또한, 이 부분은 Python 리스트의
not in을 사용하여 선형 탐색을 수행하게 되므로, 많은 양의 데이터를 다룰 때 비효율적일 수 있습니다. 집합(set)을 사용해 중복을 판별하거나 다른 방법으로 중복을 체크하는 것도 고려해볼 만합니다.문제에서 어떤 유형의 오류가 발생하는지(예: 틀린 답이 나오는지, 실행 시간 초과인지, 런타임 에러인지) 구체적인 정보가 없어 정확한 해결 방안을 찾는 데 어려움이 있습니다. 만약 오류 메시지가 있다면 그 내용을 함께 보내주시면 더 좋은 도움을 드릴 수 있을 것 같습니다.
위 사항들을 확인해 보시고, 그래도 문제가 해결되지 않는다면 인프런의 질문하기 기능을 사용해보시는 것도 좋은 방법입니다. 코드를 다시 한번 검토하시고 테스트 케이스를 다양하게 시도해 보세요.
답변 1