[제로베이스] 코테 3회차 영화보기 ( 다이나믹 프로그래밍 )

🥕 영화보기

 

🍒 문제 분석

2일간, 하루에 16시간 씩 영화를 본다.

주말 동안 시청한 영화의 총 평점의 합이 최대가 되게 하자.

 

각 영화의 소요시간이 담긴 times 리스트와 영화의 평점이 담긴 scores 리스트가 주어진다.

( 영화는 끊고 다음날  볼 수 없다. )

 

[ 입력 설명 ]

영화 갯수는 만개 이하

최대 영화 시청 시간은 16 이하

최대 영화 평점은 10점

 

[ 매개변수 형식 ]

times = [4, 6, 2, 1, 4, 6, 11, 7]

scores = [3, 5, 2, 10, 6, 2, 3, 4]

 

[ 반환 값 형식 ]

32

 

🥑 해결 과정

1. DP 테이블을 다음과 같이 구성한다.

 

2. 영화가 1개만 있을 때

시간 4, 평점 3 짜리 영화라고 한다면

 

2. 영화가 2개 있을 때

2번 영화는 시간 6, 평점 5 라고 하자.

 

 

3. 이런 식으로 영화를 순회해 나가면서 그때그때 최적행을 찾아나간다.

( 만개의 영화에 대해서 한번만 순회를 시켜주면 dp 테이블이 채워진다. )

 

4. dp[16][16] 을 반환한다.

 

 

🍓 코드

MAX_HOUR = 16

def solution(times, scores):
    dp = [[[0 for _ in range(MAX_HOUR+1)] for _ in range(MAX_HOUR+1)] for _ in range(2)]

    for i in range(len(times)):
        for t1 in range(1, MAX_HOUR + 1):
            for t2 in range(1, MAX_HOUR + 1):
                val1, val2 = 0, 0
                if t1 >= times[i]:  # 영화를 볼 수 있다면 
                    val1 = dp[(i-1)%2][t1 - times[i]][t2] + scores[i]
                if t2 >= times[i]:
                    val2 = dp[(i-1)%2][t1][t2-times[i]] + scores[i]
                dp[i%2][t1][t2] = max(dp[(i-1)%2][t1][t2], val1, val2)
    
    return dp[(len(times)-1)%2][MAX_HOUR][MAX_HOUR]

 

 

🍉 깨달은 점 및 정리