[백준/파이썬] 14728 : 벼락치기

https://www.acmicpc.net/problem/14728

14728번: 벼락치기

문제 요약 : 준석이가 시험 치는 단원의 개수N과 시험 공부할 수 있는 총 시간T가 있다. 각 단원별 예상 공부시간과 배점을 통해 준석이가 얻을 수 있는 가장 큰 점수를 구하라

 

 

배낭문제와 같은 방법으로 풀었다. 자세한 알고리즘에 대한 설명은 아래 링크를 첨부함

배낭문제 풀이

 

그런데 다른사람의 풀이를 보니 백트래킹으로 풀거나

2차원 배열을 사용하지 않고 1차원배열로 끝낸 것도 많았다

 

풀이 1 )

평범한 배낭과 똑같이 풀었음

 

dp에는 최대 점수가 저장된다

dp[ i ][ j ]에서 i는 현재과목의 번호, j는 가능한 최대 시간이다.

현재 과목을 들을 경우와 듣지 않을 경우를 비교하여 더 큰 점수를 얻는 것을 저장한다.

 

아무래도 점수이다 보니 dp의 수가 너무 커서 표로 나타내기엔 무리가 있었다.

일단 제시간안에 돌아가긴해서 맞았지만 다른 방법이 없을까 생각했다.

N,T = map(int,input().split())
study = [[0,0]] + [list(map(int,input().split())) for _ in range(N)]
dp =[[0]*(T+1) for _ in range(N+1)]

for i in range(1,N+1):
    time = study[i][0]
    score = study[i][1]

    for j in range(1,T+1) :
        if j < time :
            dp[i][j] = max(dp[i-1][j] , dp[i][j-1])
        else :
            dp[i][j] = max(score + dp[i-1][j-time], dp[i-1][j])

print(dp[N][T])

풀이 2 )

똑같은 원린데 2차원 배열을 1차원 배열로 줄였다.

N,T = map(int,input().split())
dp =[0]*(T+1)

for _ in range(N):
    time, score = map(int,input().split())

    for nowTime in range(T,time-1,-1) :
        dp[nowTime] = max(dp[nowTime], dp[nowTime-time]+score)

print(dp[T])