Q33. 퇴사

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

 

만약 이걸 전체탐색으로 풀려면

1일 상담을 잡는경우와 잡지 않는 경우로 나누고

1일 상담을 잡는경우에 잡을수 없게되는 상담들을 빼고 나머지 상담들 중에서 다시 잡을 수 있는 경우와 없는 경우를 나눠가며 탐색을 해야된다.

모든상담이 1일이 걸린다고 가정하면 전체탐색 하는데 O(2^N)이 걸리지 않을까?

 

메모화 재귀로 풀기위한 top-down 방식으로 생각을 해보려그랬는데

이건 암만 생각해도 bottom up이 더 편한 문제같다.

 

일단 내가 한 발상은

i일차에 상담을 한다고 가정했을 때

dp[i + i일차상담의 소요일수] = max(dp[i + i일차상담의소요일수], dp[i] + i일차상담수익)

이다.

이렇게해서 bottom up dp를 하면 각 상담을 할 경우와 안할경우의 최대수익을 구할 수 있다.

 

코드를 짜보았다.

N = int(input())
data = []
for _ in range(N):
    data.append(tuple(map(int,input().split())))
dp = [-1] * (N+6)
dp[0] = 0

for i in range(N):
    if dp[i] == -1:
        dp[i] = dp[i-1]

    dp[i + data[i][0]] = max(dp[i + data[i][0]], dp[i] + data[i][1])

answer = dp[N-1] if dp[N]==-1 else dp[N]
print(answer)

 

흠 근데 웬걸.. 틀렸다고 에러가나네?!

문제페이지에 있는 예시는 다 맞는데 뭐가 틀린거지?

 

정답을 볼까?

정답은 dp[i]를 i번째 날부터 마지막날까지 낼수있는 최대 이익으로 두었다.

생각해보니 이렇게해도 되겠네 신기하다

음 정답은 뭔가 다르긴 하다.

max로 비교하는 부분이 max(dp[i + data[i][0]], dp[i] + data[i][1])가 아니라 max(이전까지의 최대값, dp[i] + data[i][1])으로 하면 정답이랑 같은 맥락이 될거같다.

흐음...

 

근데 이것저것 데이터 만들어 넣어봐도 대체로 정답이 나오는데 뭐가틀린지 모르겠다..?

 

아니 계속 고민중인데 뭐가 틀린건지 모르겠다 반례를 못찾겠다;; (진짜 난 이래서 백준이 싫다)

 

나랑 비슷한 방식으로 푼 분의 코드를 봤는데 이 코드는 정상적으로 통과된다

비교해봐야겠네

 

참고해서 조금 고쳤더니 통과됐다

for i in range(N):
    dp[i + data[i][0]] = max(dp[i + data[i][0]], dp[i] + data[i][1])
    dp[i+1] = max(dp[i+1],dp[i])

 

print(dp[N])

 

아래는 통과못한 코드

for i in range(N):
    if dp[i] == -1:
        dp[i] = dp[i-1]

    dp[i + data[i][0]] = max(dp[i + data[i][0]], dp[i] + data[i][1])

answer = dp[N-1] if dp[N]==-1 else dp[N]

 

위는 통과되고 아래는 통과 안되는 반례가 뭐가있을까??;;;

 

찾았따!!!!

N = 4

3 100

1 1000

5 1

5 1

 

정답은 1000인데 내가 처음짠코드로는 100이나오네

'지금까지의 최대값'을 고려하지 않는 잘못을 저질렀다

자괴감이 한 10 적립된다. 후

 

최종 코드

N = int(input())
data = []
for _ in range(N):
    data.append(tuple(map(int,input().split())))
dp = [-1] * (N+6)
dp[0] = 0

for i in range(N):
    dp[i + data[i][0]] = max(dp[i + data[i][0]], dp[i] + data[i][1])
    dp[i+1] = max(dp[i+1],dp[i])

print(dp[N])