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

문제 : www.acmicpc.net/problem/2240

2240번: 자두나무

이론을 학습하면서 내가 잘못 생각하고 있었던걸 깨달았다.

 

DP != 완전 탐색 or 재귀

 

DP는 이미 완전 탐색 혹은 재귀로 구현할 수 있는 문제 중

빅오(n)가 너무 커서(시간 복잡도가 커서) 이를 메모이제이션 기법을 활용해서

시간 복잡도를 줄여서 TLE를 해결하는 방법이다.

 

어찌 보면 문제를 완전 탐색 or 재귀로 풀어낸 뒤에 후처리 작업하는 개념이라고 보면 되겠다.

 

여기서 문제는 내가 완전 탐색 or 재귀로 문제 풀이 전략을 세우는 걸 어려워한다.

책에서 나온 팁? 혹은 이론을 간단히 요약하면 다음과 같다.

 

어떤 문제의 해답에 더 작은 문제의 해답이 포함되어 있는 구조

(최적 부분 구조 - Optimal Substructure)를 찾아서 재귀적으로 구현.

 

그리고 책을 읽다 보니 Tip 같은 게 살짝 보였는데

1. Base(기저) 조건을 파악하는 것 - 재귀 호출을 끝내는 조건으로 사용

2. 점화식을 세울 때 시점을 가장 끝(결과)에서부터 기저 조건으로 옮겨가면서 파악하는 것

 

예제를 기준으로 n이 7일 때부터 1일 때까지 이동 횟수가 제한이 없을 경우에는

[i, j = n, 시작 위치(문제의 1을 0으로 치환, 1은 1로 치환)]

solve(i,0) = max(solve(i-1, 0), solve(i-1, 1))으로 나타낼 수 있다.

i가 7인 경우에는

sovle(7,0) = max(solve(6,0), solve(6,1))

바로 이전 스텝의 값 중 이동했을 때와 이동하지 않았을 때 최댓값을 구하면 된다.

i가 6인 경우를 전개하면

solve(6,0) = max(solve(5,0), solve(5,1))

solve(6,1) = max(solve(5,1), solve(5,0))

결국 i가 7 인건

solve(7,0) = max(max(solve(5,0), solve(5,1)), max(solve(5,1), solve(5,0)))

이렇게 해서 답을 구할 수 있다.(단, 문제에는 이동 횟수 제한이 있다.)

모든 경우의 수는 2의 n제곱 - 1이다. 처음 위치는 정해져 있기 때문에.

 

이제 이동 횟수 제한을 적용하면

[i, j, k = n, 시작 위치, 남은 이동 횟수]

solve(7,0,2) = max(solve(6,0,2), solve(6,1,1)) = max(max(solve(5,0,2), solve(5,1,1)), max(solve(5,1,1), solve(5,0,0)))

solve(6,0,2) = max(solve(5,0,2), solve(5,1,1))

solve(6,1,1) = max(solve(5,1,1), solve(5,0,0))

.... (생략)

이렇게 수식으로 나타낼 수 있다.

 

python으로 작성한 소스는 다음과 같다.

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

    def solve(n, s, c):
        if n == 0:
            return 0
        if c == 0:
            return p[n][s]

        rev_s = 0 if s == 1 else 1

        cur_side = solve(n - 1, s, c) + p[n][s]
        rev_side = solve(n - 1, rev_s, c - 1) + p[n][rev_s]

        return max(cur_side, rev_side)

    print(solve(t, 0, w))

제출을 하였으나.. 예상대로 TLE가 발생했다.

여기서 메모이제이션을 적용해서 풀어야 할 것 같은데..

2시간 동안 고민 & 시도를 거듭하였으나 풀지 못해서 일단 접어두기로 했다.

 

다음에 한번 더 고민해보고 모르겠으면 다른 사람 풀의 보고 피드백을 해야 할 것 같다.

메모이제이션까지는 아니어도 완전 탐색까지는 스스로 풀었으니 소기의 성과는 있다. 

 

하지만 속상...