2021.12.07

백준 9184 신나는 함수 실행

# 9184 ; 신나는 함수 실행
import sys

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]
    
dp = [[[0 for i in range(21)] for i in range(21)] for i in range(21)]

while True:
    a,b,c = map(int, sys.stdin.readline().split())
    if a == -1 and b == -1 and c == -1:
        break
    print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))

input()을 사용하기보다는 sys를 import 해서 시간 단축을 조금 더 해줬다.

다른 건 문제의 식을 전부 가져왔는데

중요한 아이디어는 삼차원 배열에 값을 저장해주는 것과

그 값이 있을 경우 바로바로 꺼내오는 것이 문제풀이의 핵심인 듯하다.

삼차원 배열에 저장해도 아래 코드를 쓰지 않으면 시간 초과가 뜬다.

    if dp[a][b][c]:
        return dp[a][b][c]

여담으로 아래 코드에서 공백을 안 넣어 줬더니 틀렸습니다만 계속 떠가지고 

뭐가 문제인지 한참을 찾았다...

print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))

이번 주 알고리즘 스터디의 큰 주제를 DP로 잡았다.

알고리즘 문제를 푸는 방법으로 BFS, DFS, DP 등 여러 방법들이 있지만 

오늘 풀려고 했던 문제가 DP와 관련되었고 모두 어려워해서

이번주는 DP를 단계별로 집중 탐구하는 기간으로 정했다. 

그렇기에 문제를 풀기에 앞서 DP가 무엇인지 나름대로 공부하고 이해해보고자 글을 작성한다. 

두산백과에 따르면 DP란 '다단계에 걸친 의사결정의 최적화를 추구하기 위한 수리적 계획법'이라고 한다.

너무 어렵게 적혀 있는 것 같은데 내가 이해한 DP의 핵심은 '같은 계산을 반복하지 않는 것'이다.

즉, 중복되는 부분의 값들을 메모리에 저장해 두었다가 필요할 때 꺼내 사용함으로써 

문제 풀이에 있어서 시간단축 효과를 얻을 수 있다.

DP의 방법으로 Top-Down 방식과 Bottom-Up방식의 두 가지 방식이 있다고 하는데 정확히 구분은 잘 못하겠다.

탑다운은 재귀함수를 만들어서 상위 값을 구하기 위해 하위 값을 계속해서 불러오는 것 같고,

바텀업은 하위 값부터 차례로 구해서 원하는 N번째의 값을 구하는 것 같다.

그리고 문제를 DP 방법으로 풀기 위한 조건은

1. 큰 문제를 작은 문제로 나눌 수 있다.

2.  문제의 식을 점화식으로 나타낼 수 있다.

#1463; 1로 만들기 Bottom-Up

N = int(input()) # 주어진 값 1 <= N <= 10**6
arr = [0,0,1,1] + [0]*N # N의 값의 0,1,2,3 일 때의 연산하는 최솟값, 이후 연산하는 최솟값들의 배열

for i in range(4,N+1): # N까지 연산하는 최솟값 구하기
    arr[i] = arr[i-1] + 1  # i값의 -1
    if i%3 == 0:
        arr[i] = min(arr[i], arr[i//3] + 1)
    if i%2 == 0:
        arr[i] = min(arr[i] ,arr[i//2] + 1)

print(arr[N])

바텀업 방식으로 풀어본 1463번 문제

재귀함수를 만들어서 탑다운 방식으로도 풀어보려고 했는데 능력의 한계로 인하여 실패했다...

아시는 분이 있다면 알려주세요