백준 9184 풀이 (재귀함수, 메모제이션, 다이나믹 프로그래밍)

우선 이 문제를 보고 당혹감을 감출 수 없었다.

식을 그냥 줬다. 그냥 풀어보라고 줘버린것이다.

이런건 유저가 만들어야하는데 주는 이유가 있을것이다. 처음에는 규칙을 찾아야하나?하고 고민을 했다. 솔직히 저렇게 복잡하게 얽히고 섥혀있는데 규칙을 어떻게 찾나 고민을 했다. 

그러다가 9184를 구글링 했더니 메모제이션이라는 기법이나 DP가 같이 쓰여있는 것을 확인했다.

그래서 메모제이션을 찾아보았다.

메모제이션이란 일반적인 재귀에서 이미 같은 인자를 연산했더라도 또 연산하는 경우가 존재한다. 그래서 이미 연산한 결과는 저장해두고, 만약 같은 연산이 필요할때 꺼내어 쓰자는 의도이다.

ssminji.github.io/2020/02/05/the-cake-thief/

[알고리즘] Memoization(메모이제이션) 꿀이해

자세한 내용은 고수님의 블로그로 공부하면 좋을거 같다.

 

결론은!! 반복되는 재귀연산을 줄여라!라는 문제였다.

그래서 나의 무식한 코딩으로 반복된 연산을 줄여버렸다.

코드의 내용은 그냥 무식하다. 리스트로 0으로 50,50,50 3차원배열을 만들고 연산이 진행되었을때 이걸 바로 리스트에 저장해준다. 그럼 필요할때 가져다 쓰는 방식으로 동작하게 만들었다.

memo = [[[0 for i in range(50)] for i in range(50)] for i in range(50)] 

def w(a,b,c):
    if a<=0 or b<=0 or c<=0:
        if a==-1 and b==-1 and c==-1:
            return 0
        return 1
    elif a>20 or b>20 or c>20:
        return w(20,20,20)
    elif a<b and b<c:
        sum = 0
        if memo[a][b][c-1] != 0:
            sum+=memo[a][b][c-1]
        else:
            memo[a][b][c-1] = w(a,b,c-1)
            sum += memo[a][b][c-1]
        if memo[a][b-1][c-1] !=0:
            sum+=memo[a][b-1][c-1]
        else:
            memo[a][b-1][c-1] = w(a,b-1,c-1)
            sum += memo[a][b-1][c-1]
        if memo[a][b-1][c] != 0:
            sum -= w(a,b-1,c)
        else:
            memo[a][b-1][c] = w(a,b-1,c)
            sum -= memo[a][b-1][c]
        memo[a][b][c] = sum
        return sum
    else:
        sum = 0
        if memo[a-1][b][c] != 0:
            sum += memo[a-1][b][c]
        else:
            memo[a-1][b][c] = w(a-1,b,c)
            sum += memo[a-1][b][c]
        if memo[a-1][b-1][c] != 0:
            sum += memo[a-1][b-1][c]
        else:
            memo[a-1][b-1][c] = w(a-1,b-1,c)
            sum += memo[a-1][b-1][c]
        if memo[a-1][b][c-1] != 0:
            sum +=memo[a-1][b][c-1] 
        else:
            memo[a-1][b][c-1] = w(a-1,b,c-1)
            sum += memo[a-1][b][c-1]
        if memo[a-1][b-1][c-1] != 0:
            sum -=memo[a-1][b-1][c-1]
        else:
            memo[a-1][b-1][c-1] = w(a-1,b-1,c-1)
            sum -= memo[a-1][b-1][c-1]
        memo[a][b][c] = sum
        return sum

while(1):
    a,b,c = map(int,input().split())
    t = w(a,b,c)
    if t != 0:
        print("w"+str((a,b,c))+" = "+str(t))
    else:
        break

 

결과적으로 한방에 제출을 성공했지만 코드가 너무 더럽고 중복이 많아서 다른 고수의 코드를 살펴보기로 했다.

upcount.tistory.com/8

MAX = 21
dp = [[[0]*MAX for _ in range(MAX)] for __ in range(MAX)]
 
def w(a, b, c) :
    if a<=0 or b<=0 or c<=0 :
        return 1
    if a>20 or b>20 or c>20 :
        return w(20, 20, 20)
 
    # 값이 이미 존재한다면 그 값을 바로 리턴.
    if dp[a][b][c]:
        return dp[a][b][c]
 
    if a<b<c :
        dp[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return dp[a][b][c]
 
    dp[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
    return dp[a][b][c]
 
while True :
 
    a, b, c = map(int, input().split())
 
    if a== -1 and b==-1 and c==-1 :
        break
 
    print("w(%d, %d, %d) = %d"%(a, b, c, w(a, b, c)))

 

그냥 불필요한거 다 줄이고 값이 존재하면 바로 값을 리턴하게 만들고 아니라면 연산을 진행하도록 하는 방식으로 코드를 짜셨다. ㄷㄷ이다.

더 신중히 코드를 짜야겠다.

 

찾아보니 동적프로그래밍 중 하나가 메모제이션이라고 한다. 즉, 기억하는 프로그래밍이라고 한다.