파이썬 - 다이나믹 프로그래밍(dynamic programming) 실전 문제

목차

-시작

-문제 1: 백준 - 1, 2, 3 더하기

-문제 2: 백준 - 정수 삼각형

-문제 3: 백준 - 스티커

-문제 4: 백준 - 평범한 배낭

-문제 5: 최장 공통부분 문자열 <-- 준비중

-문제 6: 곱하기 최댓값 구하기 <-- 준비중

-문제 7: 프로그래머스(카카오) - 광고 삽입 < -- 준비중

-문제 8: 릿코드 (https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/) <-- 준비중

-문제 9:

시작 

이번 시간에는 다이나믹 프로그래밍 유형 학습을 위해 문제를 풀어봅시다.

다이나믹 프로그래밍이 다양한 유형이 있다고 한들 유한합니다.

유형이 많으면 많이 풀어보면 그만입니다.

그러면 들어가 봅시다.

문제 1 : 백준 - 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

문제는 이렇습니다.

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

문제를 읽고 드는 생각

예제에 대해서 tree를 그려보고 싶었을 것입니다.

자 그럼 tree를 그려봅시다.

만약 tree를 그려야 한다는 생각이 안드 셔 더라도 괜찮습니다.

저번에 학습한 dp를 복습하고 이 문제를 3일 뒤에 다시 풀어 보면 됩니다.

그러면 자신의 지식으로 축적시킬 수 있습니다.

그래프를 보니 문제에서 요구한 모든 경우의 수가 전부 찾을 수 있습니다.

이를 구현하면 정답 판정을 받을 수 있을 것 같습니다.

 

그러면 앞에서부터 해봅시다.

n이 1일 때부터 시작해서 4일 때까지 진행해 봅시다.

자 여기서 패턴을 발견해보면?

f(n)을 구한다고 한다면  m + f(n-m), f(n-m) + m ( m = 1, 2, 3)의 값을 모든 m에 대하여 집합 연산을 진행하면 얻을 수 있는 패턴을 발견할 수 있습니다.

 

여기서 좀 더 생각해 보면 아래와 같은 패턴을 찾을 수 있습니다.

사람들의 사고방식에 따라 앞에서 보는 것이 편한 분들도 있고 뒤에서 보는 분들이 편한 분들도 있습니다.

하지만 저희는 모두 다 해야 합니다.

익숙해지면 대부분 앞에서 생각하고 for loop로 구현하기는 합니다.

하지만 저희는 학습하는 입장이기에 모두 다 합시다.

 

의사 코드

상대적으로 recursion구현이 쉽습니다.

그러니 for loop로 구현해 봅시다.

for loop 중에서도 처음 생각한 패턴으로 진행해 봅시다.

 

문제를 보면 여러 개의 값을 리턴해야 합니다.

그리고 N이 작은 수로 한정되어있습니다.

모두 다 계산하여 저장했다가 이 값을 이용하여 print 하는 전략을 사용합시다.

이러한 테크닉은 코딩 테스트에서 많이 사용됩니다.

뭔가 적은 값을 지속적으로 리턴해야 된다고 느껴지면 모두 계산하여 저장했다 사용합시다.

1. dp = [set()] * (N)로 초기화합니다.

2. dp [1]부터 dp [3]까지 초기 조건을 넣습니다.

3. for i in 4 ~ n 

    dum = set()

    for m in 1 ~ 3

       sm = str(m)

        for ele in dp[i-m]

            dum.add(sm+ele)

            dum.add(ele+sm)

    dp[i] = dum

 

구현

아래의 구현 말고도 위에서 생각했던 다양한 방법을 구현해 보면 좋습니다.

처음 dp를 접하시는 분은 무조건 구현해봅시다.

# 백준에서 인풋을 받는 방법이다.
test_case=int(input())

input_list=[]
for i in range(test_case):
    input_list.append(int(input()))


#우리가 찾은 패턴을 구현한 곳이다.
N = 10
dp = [set()]*N
dp[0] = {'1'}
dp[1] = {'11', '2'}
dp[2] = {'111', '21', '12', '3' }

for i in range(3,N):
    dummy = set()
    for m in range(1,4):
        stm = str(m)
        for ele in dp[i-m]:
            dummy.add(stm+ele)
            dummy.add(ele+stm)
    dp[i] = dummy

for i in input_list:
    print(len(dp[i-1]))

문제 2 : 백준 - 정수 삼각형

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

1932번: 정수 삼각형

문제는 이렇습니다.

피라미드 형태의 정수형 데이터가 주어집니다.

예를 들면 아래와 같은 형태는 크기가 4인 삼각형입니다.

맨 위부터 시작해 아래로 내려올 때 합이 최대가 되는 경로를 찾는 문제 입다.

내려올 때는 선택된 수의 대각선 왼쪽 혹은 오른쪽으로 내려옵니다.

예를 들어 그림은 5번에서 내려올 수 있는 방법은 2와 3입니다.

 

(1 ≤ n ≤ 500)

 

문제를 보면 드는 생각.

이 문제 또한 tree를 그릴 생각을 해야 합니다.

예시 그림에서 삼각형 아래의  2에 대한 tree를 그려봅시다.

2에서 꼭대기 8 로가는 경로는 총 3가지가 존재합니다.

3가지의 경로중 최댓값을 찾는 방법은 위의 그림과 같이 recursion으로 처리하면 정답 판정을 받을 수 있을 것 같습니다.

꼭대기에 도착을 하면 정수 8을 이전 노드로 리턴합니다.

이전 노드는 자신의 값과 리턴 받은 값을 더 합니다.

만약에 경로가 2개여서 리턴을 2곳 에서 받는다면 max() 함수를 이용하여 큰 값을 리턴하면 됩니다.

 

그럼 앞에서부터 생각해 봅시다.

아래의 그림은 5로 가는 경로중 가장 큰 값을 찾는 상황입니다.

꼭대기에서 꼭대기로 갈 수 있는 최댓값은 8입니다.

그다음 경로인 7로 가는 최댓값은 7+8이고 6은 8+6입니다.

5번의 경우 7번과 6번에서 들어갈 수 있습니다.

모든 경로중 최댓값을 선택하면 5번까지의 경로 최댓값을 구할 수 있습니다.

이와 같은 패턴으로 맨 아래까지 진행하면 될 듯합니다.

 

의사 코드

recursion부분은 각자 해보고 for loop로 구현해 봅시다.

1. dp[깊이][행]을 입력받은 데이터로 초기화 시킵니다.

2.  for i in 1 - 깊이:

         for j in 행 = 깊이 +1:

             if j == 0:  

                 dp[i][0] += dp[i-1][0]

             elif j == 마지막:

                 dp[i][j] += dp[i][j-1]

             else:

                 dp[i][j] += max(dp[i][j], dp[i][j-1])

3. dp[-1]의 성분을 이용하여 정답을 제출합니다.

 

구현

height = n
dp = [ [0]*i for i in range(1,height+1) ]

for depth in range(height):
    for row in range(depth+1):
        if row == 0:
            dp[depth][row] = dp[depth][row]
        elif row == depth:
            dp[depth][row] = dp[depth][row-1]
        else:
            dp[depth][row] = max(dp[depth][row], dp[depth][row-1]) 
            
print(max(dp[-1]))

 

문제 3 : 백준 - 스티커

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

9465번: 스티커

문제는 이렇습니다.

2줄짜리 스티커가 주어 집니다.

스티커마다 숫자가 있습니다.

스티커 1개를 때어 내면 상하좌우의 스티커도 같이 때어져 나갑니다.

이런 상황에서 떼어낸 스티커의 숫자의 합이 최대가 되는 값을 구하는 프로그램을 작성하면 됩니다.

 

(스티커의 길이는 n이라 표현하고  1 <= n <= 100,000이다)

 

문제를 읽고 드는 생각

자 이런 문제는 문제를 읽고 구속조건을 만들어야 합니다.

잘 관찰하다 보면 첫 칼럼의 스티커는 무조건 1개가 때어지게 됩니다.

왜 그럴까요?

그림을 봅시다.

무지 성으로 뜯어도 첫 줄은 둘 중 하나가 떄어집니다.

 

자 그럼 첫 번째 칼럼 중 위의 성분이 제거되었다고  생각을 하고 우리가 하던 대로 tree를 그려봅시다.

위처럼 recursion으로 구현하고 저장된 집합 중 값이 가장 큰 걸 선택하면 되지만.

문제 조건에서 행의  길이가 100,000이라 좀 더 효율적으로 변화시켜야 합니다.

지금의 방법을 그대로 사용한다면 집합을 구하는데 O( (n-3)*(n-6)*.. *2*1)의 시간 복잡도를 가집니다. 

 

여기서 패턴을 발견해 탐색 수를 줄여봅시다.

0번을 선택하고 다음에 선택할 수 있는 경우의 수는 현재 {5, 6, 7, 2 }입니다.

위의 그림에서 0번을 칠하고 2번을 칠하는 경우를 카운트하는 게 의미가 있을까요?

의미가 없습니다.

결과를 보면 0번과 5번을 칠한 부분과 겹칩니다.

왜 그런 걸까요?

위 그림은 0번과 2번을 선택한 경우를 나타낸 것입니다.

우리는 최댓값을 구해야 하기 때문에 5번은 강제로 선택이 되어야 합니다.

그래서 고려되는 대상이 {5, 6 ,7}로 줄었습니다.

 

이번엔 0과 7을 선택한 경우를 봅시다.

5번을 무조건 선택이 되어야 합니다.

그래서 고려되는 대상이 {5, 6}으로 줄었습니다.

 

0과 6의 경우를 생각해 보면.

5랑 전혀 다른 경우입니다. 

결국 0번을 선택하면 {5, 6} 번을 선택하는 2가지 경우가 있습니다.

 

이 패턴을 일반화해보면

위와 같은 상황이 고려되어야 합니다.

여기까지 고려하면 시간 복잡도는 O(2**n) 정도입니다.

조금 더 노오오력을 해야 합니다.

 

다시 패턴을 찾기 위해 방금 구한 사실을 이용하여 tree를 그려봅시다.

반복이 되는 패턴이 보이는군요.

위의 경우는 0부터 시작한 경우입니다.

처음 시작 조건을 0과 6을 둘 다 고려해야 하는데 만약 0에 대해서 탐색이 끝이 났다고 생각을 해봅시다.

그러면 6의 경우 0에서 구한 사실들 때문에 O(1)으로 처리할 수 있습니다.

반복되는 부분을 제거하여야 다시 보기 좋게 tree를 그려봅시다.

반복되는 부분을 고려하면 위와 같이 줄일 수 있습니다.

memo를 사용하면 시간 복잡도는 O(n)으로 n = 100,000일 때 충분히 해결 가능합니다.

 

이 번엔 앞에서부터 생각해 봅시다.

앞에서부터 차례대로 선택을 하였고 현재 가운데의 시티 커를 선택했다고 가정해봅시다.

이 상황에서 최댓값이 되기 위해서는 이전의 선택은 최댓값을 가지는 선택이어야만 합니다.

어떻게 하면 최고의 선택을 하며 진행할까요?

예시를 생각해 봅시다.

위 그림에서 표시된 선까지 최댓값이 계산되었다고 가정해봅시다.

100이 선택되는 방법의 수는 위의 그림에서 동그라미로 표시되는 방법입니다.

그렇기에 100의 최댓값은 max( "아래 30까지의 최댓값" + 100, "아래 50까지의 최댓값" + 100)입니다.

마찬가지로 60의 최댓값은 max("위에 50까지의 최댓값" + 60,   "아래 50까지의 최댓값" + 60)입니다.

 

실전 문제를 풀다 보면 dp를 보는 감이 생길 것입니다.

그 감을 여기서 한번 정리해봅시다.

일단 dp문제를 보면 대략적으로 이러한 프로세스로 생각을 해야 합니다.

1. 무슨 알고리즘을 써야 할지 모르겠는데 전부 해보면 되겠다.

2. 근데 문제 인풋을 보니 선형 탐색으로 해야겠네? 이걸 어쩌나

3. dp문제인가?

4. 그럼 일단 예제부터 손으로 해보면서 힌트를 찾자

4. 이 힌트를 가지고 점화식을 찾으면 좋겠네

5. 그럼 i-1까지 되어 있다고 생각을 하고 i번째를 생각해 봐야겠다.

6. 초기 조건이랑 탈출 조건 잘해서 구현해야겠다.

 

의사 코드 

for loop로 구현해 봅시다.

recursion 구현은 각자 해봅시다.

1. dp[i][j] = number  i= 높이 j = 너비 로 초기화 시킨다.

2. for j in range(n) 를 돈다.

       dp[0][j] += max(dp[1][j-2]  , dp[1][j-1])

       dp[1][j] += max(dp[0][j-2] , dp[0][j-1])

3. dp의 마지막 컬럼중 최댓값을 제출한다.

 

구현

T = int(input())
for _ in range(T):
    n = int(input())
    dp = [ list(map(int, input().split())) for _ in range(2) ]
    if n == 1:
        print(max(dp[0][0], dp[1][0]))
    else:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]
        for i in range(2,n):
            dp[0][i] += max(dp[1][i-1], dp[1][i-2])
            dp[1][i] += max(dp[0][i-1], dp[0][i-2])
        print(max(dp[0][n-1], dp[1][n-1]))

문제 4: 백준 - 평범한 배낭

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

12865번: 평범한 배낭

문제는 이렇습니다.

재한 된 무게 k를 담을 수 있는 배낭이 있습니다.

배낭에 담을 물건들은 N개가 있고 각각 물건들은 무게 w와 가치 v를 가지고 있습니다.

이때 배낭에 담을 수 있는 최대 가치를 구하는 문제입니다.

 

단

물품의 수 N(1 ≤ N ≤ 100)

무게 K(1 ≤ K ≤ 100,000

W(1 ≤ W ≤ 100,000)

V(0 ≤ V ≤ 1,000)

 

문제를 읽고 드는 생각

모든 경우를 전부 해보고 최댓값을 구해면될듯합니다.

하지만 인풋 값을 보니 모든 경우를 다 고려하면 시간 초과입니다.

dp문제인 것을 인지하고 패턴을 발견해 봅시다.

패턴을 발견하기 위해 주어진 예제를 가지고 놀아봅시다.

 

dp의 경우 i번째를 구하기 위해서는 i번째 이전의 값을 이용하여 구합니다.

무게에 따라 가치가 달라지고 가치의 최댓값을 구할 수 있으니 dp의 변수를 무게로 해서 생각해봅시다.

dp [W] =  V (W = 물품들의 무게 합이다, V = 물품들의 최대 가치 합이다)

위의 그림은 dp [7]까지 노가다로 계산한 결과입니다.

그럼 'dp[8] = ?'에서 '?'에 해당하는 점화식은 뭘까요?

최댓값을 만들 수 있는 경우의 수를 생각해봅시다.

{dp [7]+dp [1], dp [6]+dp [2], dp [5]+ dp [3], dp [4]+dp [4], 물품 중 무게가 정확히 8인 물품 }

이 있을 것입니다.

이중 최댓값을 구하면 될 듯합니다.

max(dp [7]+dp [1], dp [6]+dp [2], dp [5]+ dp [3], dp [4]+dp [4], 물품 중 무게가 정확히 8인 물품)

이 패턴을 사용하면 시간 복잡도는 O(n * n // 2)입니다.

안 될 거 같죠?

혹시 모르니까 시도나 해볼까? 힘만 낭비한다. 시도도 하지 말자!

조금 더 효율적으로 만들어 봅시다.

 

문제의 조건을 보면 물품의 수가 100개로 적습니다.

일단 물품들의 집합을 item = {w : val }요런 식으로 나타낸다고 생각합시다.

그러면 dp [8]의 후보가 될 수 있는 애들은 {dp [w + i] + item [w], i+w = 8,  }입니다.

여기까지 생각하면 시간 복잡도는 O(n*100) = O(n)으로 선형 시간에 해결할 수 있습니다.

 

의사 코드

1. 인풋을 입력받는디ㅏ.

2. dp[W] = 0과 item = { w : v }를 만든다.

3. for i in range(k+1):
        dummy = []
        for w, v in item.values():
            if i-w >= 0:
                dummy.append(dp[i-2] + v)
4. 정답을 제출한다.

구현

준비중 .....
필자가 a형 간염에 결려 쉬어야 한다...
구현하는거 너무 귀찮고 힘든 일이다..

문제 5 : 최장 공통부분 문자열

문제

문자열 2개가 인풋으로 주어집니다.

이때 최장 부분 문자열의 크기를 리턴하세요.

 

구속 조건

1 <= 두 문자열의 길이 <= 1000

 

ex)

t1 = 'aaabbbcccc'

t2 = 'adbcdda'

 

문제를 읽고 드는 생각

문제를 읽으면 무지성으로 완전탐색을 진행하면 정답 판정을 받을 수 있을 것 같습니다.

하지만 이 문제는 잘 알려진 dp문제입니다.

dp관점에서 생각을 해봅시다.

 

dp를 구현하기 위해 dp의 차원에 대해 먼저 생각해봅시다.

dp [i]처럼 1차원으로 가능할까요?

불가능합니다.

dp [i]를 사용한다는 말은 for loop를 한번 사용한다는 말과 같습니다.

하지만 문자열이 2개 존재합니다.

만약 한 번으로 가능하기 위해서는 두 문자열을 인댁스가 f(i) = j처럼 함수로 연결되어 있어야 합니다.

하지만 문제에 주어진 두 문자열의 인덱스는 독립되어 있습니다.

결국 for loop 두 개를 사용해야 하므로 2차원 변수를 가지는 dp [i][j]를 사용해야 합니다.

 

자 이제 체크해야 하는 일은 이전의 결과가 다음 연산에 사용될 수 있느냐를 판단해야 합니다.

이런 구조를 발견하기 위해 임의의 상황에 대해 손으로 그려봅시다.

(그림)

손으로 그려보니 쉽습니다. 근데 어떻게 구현하지?

먼저 2개의 문자열을 종이에 기록합니다.

text1의 문자열을 기준으로 text2에 부분 문자열을 찾습니다.

같은 문자열은 선으로 연결합니다.

하지만 순차적으로 배열이 되어 있어야 합니다.

선이 교차하는 경우는 제외하고 진행해야 합니다.

 

근데 여기서 느껴야 합니다.

우리는 손으로 표시한 선을 종이에 기록해 두었다가 사용하고 있습니다.

또한 선을 그릴 곳을 찾는 행위는 for loop를 이용하여 구현하면 됩니다.

text1의 문자를 text2에 해당하는지 찾고 있기 때문에 2중 for loop를 사용하면 됩니다.

text2 for loop의 경우 선이 겹치면 안 되기 때문에 마지막에 찾은 인덱스부터 탐색하면 됩니다.

 

손으로 표시한 선을 어떻게 하면 구현 가능할까?

쉽게 생각해 보면 데이터 구조를 선택하고 저장하면 됩니다.

이번 문제의 경우 선의 수만 카운트하면 됩니다.

그러니 text1의 i번째 text2의 j번째 까지 확인한 선의 수를 dp [i][j]에 보관하여 사용합시다.

손으로 할 때 선이 겹치지 않고 text1 [i] = text2 [j]의 경우 선을 그리고 추가했습니다.

그러니 만약 조건에 맞는 선을 찾았다면 dp [i][j] = dp [i-1][j-1]로 업데이트해주면 됩니다.

선이 겹치지 않는 조건은 마지막에 찾은 조건을 기록해 두었다가 이후의 경우만 탐색하게 for loop를 구현해 봅시다.

선이 겹치지 않는 조건은 text2에서 확인된 마지막 인덱스를 변수에 저장해 두었다가 다음번 for loop를 돌 때 확인된 이후부터 체크하도록 구현해 봅시다.

 

이렇게 정리한 내용은 다시 한번 손으로 체크해 봅시다.

구현하기 이전에 그림을 그려 한 번 더 확인하면 끝 인덱스 처리에 오류가 있는지 확인해 볼 수 있습니다.

꼭 한 번 더 그려봅시다.

(그림)

 

 

 

구현

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    dp = [[0 for _ in range(len(text2)+1) ]  for _ in range(len(text1)+1) ]
    answer = 0
    for i in range(1,len(text1)+1):
        for j in range(1,len(text2)+1):
            if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

 

문제 6 : 곱하기 최댓값 구하기

문제

숫자들의 모음 nums와 곱할 때 사용할 muls가 인풋으로 주어집니다.

점수 0부터 시작하여 아래의 조건을 만족하는 연산을 len(muls)만큼 진행하여 최댓값을 만들어야 합니다.

아래의 조건은 len(muls) 번의 연산중 i번째 연산을 나타낸 것입니다.

• nums의 앞의 값 혹은 뒤의 값 중 1개를 선택하고, nums에서 제거합니다. 이를 a라고 합시다.
• nums에서 뽑은 a를 muls [i]와 곱하고 i-1번째 가지 계산된 점수에 더한다.

구속조건

muls의 길이는 nums의 길이와 작거나 같습니다. len(nums) >= len(muls)

ex)

nums = [ 3, -2, -5, -2, -7 ]

muls = [ 3, 4, 2, -2 ]

 

문제를 읽고 드는 생각

dp문제들은 대부분 무지성으로 풀이가 가능합니다.

이제 무지성은 귀찮으니 언급하지 않겠습니다.

알아서 구현해 봅시다.

 

이 문제를 보니 dp느낌이 스멀스멀 올라옵니다.

최댓값을 구해야 하고, 여러 가지 선택지가 존재하기 때문입니다.

그러면 그림을 그려보며 확인해 봅시다.

(그림)

그림을 그리고 중간에 확인하는 과정에서 이전의 결과를 다음에 사용하는군요.

dp가 확실합니다.

그러면 dp분석을 들어가 봅시다.

 

dp구현을 위해 dp의 차원부터 조사해봅시다.

일단 i번 곱해야 합니다. 그러니 muls의 for loop를 위한 차원이 존재해야 합니다.

또 다른 차원이 필요할까요?

nums에서 왼쪽 선택과 오른쪽 선택의 자유도가 있습니다.

이는 muls의 for loop와 독립적입니다.

결국 muls에 대한 차원 i, nums의 왼쪽 또는 오른쪽 선택에 대한 차원 j가 존재합니다.

여기서 j가 어떤 의미를 가지는지 명확하게 하기 위해서는 임의의 상태에서 과거를 보고 판단해야 합니다.

i번째 까지 진행된 상태이고 왼쪽 연산이 k번 오른쪽 연산이 i-k번 진행된 상태라 가정해봅시다.

과거에서 이 상태에 올 수 있는 방법은

• i-1번째 진행된 상태이고 왼쪽 연산이 k-1번 오른쪽 연산이 i-k 진행된 상태에서 왼쪽 연산을 하는 경우
• i-1번째 진행된 상태이고 왼쪽 연산이 k번 오른쪽 연 사이 i-k-1번 진행된 상태에서 오른쪽 연산이 진행된 경우

2가지입니다. 

dp는 위와 같은 상황을 적절히 묘사하기 하고 결과를 기록하기 위한 자료구조 이므로 적절하게 선택하여 사용하면 됩니다. 저의 경우 dp [i] = i번째 곱하기 ] [j = 왼쪽 연산의 수 ] = socre로 정의해 사용할 것입니다.

 

dp [i][j] = score를 이용하여 최댓값을 구해야 합니다.

어떻게 하면 구할 수 있을까요?

만약 m-1번 까지 최댓값으로 dp [i][j]를 구했다 생각해 봅시다.

그럼 마지막에 왼쪽과 오른쪽 중 가장 값이 큰 값을 선택하여 더하면 m번까지의 최댓값을 구할 수 있습니다.

요런 식의 논리를 m-2번과 m-1에 대해 생각해 보면 m-2번째 최댓값을 구하고 왼쪽과 오른쪽 중 최댓값을 선택해 더하면 m-1번째 최댓값을 구할 수 있습니다.

이를 0번째 까지 진행해 보면 전부 성립합니다.

그래서 임기의 i에 대해 아래와 같은 점화식을 구할 수 있습니다.

dp [i][j] = max(dp [i-i][j-1] + nums [왼쪽]*muls [i], dp [i-1][j] + nums [오른쪽]*muls [i]) 

결국 문제에서 원하는 최댓값은 i에 대해 for loop를 전부 수행했을 때 dp의 마지막 성분입니다.

 

끝 인덱스 오류 및 구현의 정확성을 위해 위의 점화식으로 작동하는 그림을 한 번 더 작성해봅시다.

(그림)

 

구현

어후 힘들어 구현은 나중에

 

 

https://programmers.co.kr/learn/courses/30/lessons/12971

코딩테스트 연습 - 스티커 모으기(2)

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

 

https://programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

 

 

https://programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

 

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/

Minimum Difficulty of a Job Schedule - LeetCode