문제풀이 이론 학습 #2-2

원래는 어제 끝냈어야 하는 건데.. 마무리를 못지어서 오늘까지 같은 주제로 포스팅을 한다.

 

20분 정도 다시 생각 및 풀어보는 시도를 했지만

결국 실패해서 다른 사람의 풀이를 참조했다.

(travelbeeee.tistory.com/52)

 

풀이를 보고 느낀 건,

내가 아주 틀린 방향으로 가고 있진 않았다.

재귀로 작성한 함수의 arguments가 3개였으므로

메모이제이션을 구성할 때(dp 배열) 역시 3차원으로 구성해야 하는 걸 알게 됐다.

그리고 재귀는 마지막 결과로부터 기저 조건을 향해 가는 걸 중점으로 로직을 짜야 하나

메모이제이션의 경우 기저 조건부터 값을 누적해가는 로직으로 짜야한다.

 

해당 문제의 상세한 풀이에 대한 건 상기의 블로그를 참조하면 되고

초기값을 설정하는 부분과 메모이제이션 해가는 부분을 중점적으로 보면 될 것 같다.

 

근래에 dp 문제 몇 개를 접해보고 느낀 점은

dp는 누적 값(최대/최소)에 대한 생각을 깊이 해봐야 되는 거 같다.

 

파이썬으로 작성한 코드는 다음과 같다.

if __name__ == "__main__":
    t, w = map(int, input().split(' '))
    p = [0 for _ in range(t + 1)]
    for i in range(1, t + 1):
        p[i] = int(input())

    dp = [[[0, 0] for _ in range(w + 1)] for __ in range(t + 1)]

    for i in range(1, t + 1):
        dp[i][0][0] = dp[i - 1][0][0]
        dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0])
        if p[i] == 1:
            dp[i][0][0] += 1
        else:
            dp[i][1][1] += 1

    for i in range(2, t + 1):
        for j in range(1, w + 1):
            dp[i][j][0] = max(dp[i - 1][j - 1][1], dp[i - 1][j][0])
            dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1])
            if p[i] == 1:
                dp[i][j][0] += 1
            else:
                dp[i][j][1] += 1

    result = 0
    for j in range(w+1):
        for k in range(2):
            if dp[t][j][k] > result:
                result = dp[t][j][k]
    print(result)

dp의 다른 문제를 또 도전할 예정이며

참고서적의 다른 섹션의 알고리즘을 익혀서 풀어볼 생각이다.

 

조금 아쉽다.. 골대 앞에서 결정력이 부족해서 골을 못 넣은 것 같은 기분이다.