글 읽기 - 14%에서 틀리는데 잘못된 부분을 못찾겠습니다

ghks2047 2년 전 0

재귀로 완전탐색을 수행했구요. 예제 전부 통과하지만 14%에서 틀립니다.

반례를 못찾겠어서 이렇게 글 남깁니다.

N = int(input())

days = [[]]
for i in range(N):
    days.append(list(map(int, input().split())))

max_money = 0


def calc(day, cost):
    global max_money
    # 해당일에 일을 할 수 있는 경우
    if day <= N and day + days[day][0] <= N+1:
        # 일을 하는 경우
        calc(day+days[day][0], cost+days[day][1])
        # 일을 안하는 경우
        calc(day+1, cost)
    else:  # 일을 할수없는 경우
        if cost > max_money:
            max_money = cost


# 시작 일
for i in range(1, N+1):
    if i + days[i][0] <= N+1:
        calc(i+days[i][0], days[i][1])
print(max_money)

ghks2047 2년 전 0

자답합니다.

알고보니 18번째 줄에서 연산이 안되는 경우

바로 값을 max_value와 비교하는게 아니라 다음날짜로 넘어가는 경우가 추가되어야 했습니다.

    # 해당일에 일을 할 수 있는 경우
    if day <= N and day + days[day][0] <= N+1:
        # day 부터 일을 하는 경우
        calc(day+days[day][0], cost+days[day][1])
        # 일을 안하는 경우
        calc(day+1, cost)
    else:  # 일을 할수없는 경우
        # 다음날로 넘어간다
        if day < N:
            calc(day+1, cost)
        if cost > max_money:
            max_money = cost

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

문제

문제

출처

ICPC

14%에서 틀리는데 잘못된 부분을 못찾겠습니다

ghks2047 2년 전 0

ghks2047 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말