파이썬 알고리즘 134번 | [백준 9184번] 신나는 함수 실행

134. 신나는 함수 실행

1) 어떤 전략(알고리즘)으로 해결?

• 3차원 arr에 미리 선언해두고 그때 그때 빼오기

2) 코딩 설명

<내 풀이>

arr=[[[0  for _ in range(21)]for _ in range(21)]for _ in range(21)]
arr[0][0][0]=1
for a in range(21):
    for b in range(21):
        for c in range(21):
            if a ==0 or b==0 or c==0:#a,b,c가 0인 경우
                arr[a][b][c]=1
            else:
                if a<b and b<c : 
                        if c==1:#c가 1인 경우
                            arr[a][b][c-1]=1
                            arr[a][b-1][c-1]=1
                        if b==1 :#b가 1인 경우
                            arr[a][b-1][c-1]=1
                            arr[a][b-1][c]=1
                        arr[a][b][c]=arr[a][b][c-1] + arr[a][b-1][c-1]-arr[a][b-1][c]
                else :
                    if a==1:
                        arr[a][b][c]=2
                    else : 
                        if b==1:
                            arr[a-1][b-1][c]=1
                            arr[a-1][b-1][c-1]=1
                        if c==1:
                            arr[a-1][b][c-1]=1
                            arr[a-1][b-1][c-1]=1
                        arr[a][b][c]=arr[a-1][b][c] + arr[a-1][b-1][c]+arr[a-1][b][c-1]-arr[a-1][b-1][c-1]
# print(arr[20][20])
a,b,c=map(int,input().split())
while (a!=-1 or b!=-1 or c!=-1):
    if a<=0 or b<=0 or c<=0 : 
        print("w(%d, %d, %d) = 1" %(a,b,c))
    elif a > 20 or b > 20 or c > 20 :
        print("w(%d, %d, %d) = %d" %(a,b,c,arr[20][20][20]))
    else : 
        print("w(%d, %d, %d) = %d" %(a,b,c,arr[a][b][c]))
    a,b,c=map(int,input().split())

<다른 분의 dp 풀이>

출처 : 출처

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)))

<반성 점>

• 나 너무 다 선언하고 데려오는 방식으로만 구현하는 듯
• 이럼 너무 곤란해 더 발전적으로 dp 사용 원해

<배운 점>

배열 생성
2,3차원 배열 생성 출처 블로그

1. 2차원 배열 생성하기

2d_arry = [[0 for _ in range(column)] for _ in range(row)]

2. 3차원 배열 생성하기

3d_array = [[[0 for _ in range(column)] for _ in range(row)] for _ in range(level)]

2~3중 반복문을 선언함에 따라서 'range'의 파라미터는 열(컬럼) → 행(로우) → 층(레벨)의 순서로 선언하면 되며, 최초 초기화할 값 (0, None... 등)에 따라 선언이 완료