9184번 - 신나는 함수 실행

문제에 주어진 코드를 실행시키려고 하는데
문제에서 해당 코드를 실행시키면 시간이 너무 오래걸릴까봐 걱정이랍니다.
해당 코드를 시간초과가 나지 않게 실행시키는 코드를 작성하면 됩니다.

...보자마자 짐작이 갑니다. DP의 메모이제이션 기법을 사용하면 됩니다.

---

분석

보통 팩토리얼같은데서 메모이제이션을 사용하면 변수를 하나만 받아서 memo[해당변수] 라는 씩으로 기록하는데 이번에는 변수가 무려 세 개입니다.

보고 딱 떠오른 생각은 3차원 리스트로써 memo[a][b][c] 로 구현하는게 정해겠구나 생각했습니다.

그러나 저는 남들과 같은 길을 걷기는 싫어 조금 창의적으로 구현해봤습니다.

일단 메모이제이션으로써 딕셔너리를 하나 만들고, 3개 변수를 묶은거

(예를 들어 w(20,20,20) 이라면 dict['202020'] = 해당 재귀문 (w(20,20,20)이라던가 w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) 와 같은 등등...) )

와 같은 형식으로 딕셔너리를 구성해준 후

    if str(a)+str(b)+str(c) in memo.keys():
        return memo[str(a)+str(b)+str(c)]

해당 값이 key값에 존재한다면 해당 값의 key에 해당하는 value를 내보내는 식으로 구현해도 될 것 같았습니다.

---

첫번째 시도

while True:
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print('w(%s, %s, %s) ='%(a,b,c),w(a,b,c))

먼저 문제에서 -1,-1,-1이 들어오면 입력을 멈추고 그 전까지는 출력하라 했으므로 위와 같이 출력 형식에 맞추어 코딩해줍니다.

memo = dict()

def w(a,b,c):

다음으로 메모이제이션으로써 딕셔너리를 하나 선언하고 w함수 제작을 시작합니다.

    if str(a)+str(b)+str(c) in memo.keys():
        return memo[str(a)+str(b)+str(c)]

아까 말한대로 현재 탐색중인 값이 메모이제이션의 키값에 있으면 해당 value 값으로 return 해줍시다.

    if a>20 or b>20 or c>20:
        memo[str(a)+str(b)+str(c)] = w(20,20,20)
        return memo[str(a)+str(b)+str(c)]

나머지는 문제에 나온 코드 그대로 작성하되 메모이제이션 기법을 사용할 수 있게 메모이제이션에 넣어 해당 메모이제이션 값으로 return 해주도록 합시다.

    if a>20 or b>20 or c>20:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(20,20,20)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

    if a<b and b<c:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]
    else:
        memo[str(a)+'empty'+str(b)+'empty'+str(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 memo[str(a)+'empty'+str(b)+'empty'+str(c)]

나머지도 동일한 방식으로 작성하면 됩니다.
이제 출력해보니까

값은 잘나오는데

알수 없는 이유로 틀립니다.

---

오답 원인 분석

곰곰히 생각해보니까 메모이제이션 작성을 할때 w(11,11,11)과 같은 형식을 기재받게 되면 memo['111111']이 되는데

이게 나중에 메모 참고를 할때 w(1,111,11)이냐, w(1111,1,1)이냐 구분할 방법이 없기 때문에 나는 오류라고 생각이 됩니다.

그래서 w(a,b,c)사이를 구분해줄 문자를 아무거나 하나 넣어주기로 했습니다.

---

해결

memo = dict()

def w(a,b,c):

    if a<=0 or b<=0 or c<=0:
        return 1

    if str(a)+'empty'+str(b)+'empty'+str(c) in memo.keys():
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]
    
    if a>20 or b>20 or c>20:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(20,20,20)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

    if a<b and b<c:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]
    else:
        memo[str(a)+'empty'+str(b)+'empty'+str(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 memo[str(a)+'empty'+str(b)+'empty'+str(c)]
    
while True:
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print('w(%s, %s, %s) ='%(a,b,c),w(a,b,c))

단순히 a와b사이, 그리고 b와 c사이 메모이제이션을 원활히 참고될 수 있도록 'empty'라는 문자열을 넣어 구분해주기로 했습니다.

---

---

11057번 - 오르막 수

위와 같이 자리수가 주어졌을 때 해당 자리수에서 나올 수 있는 오르막 수가 나오는 경우를 모두 구하는 문제입니다.

---

분석

일단 저 위에 0,1,2,3,4,5,... 는 마지막 자릿수입니다.
그러니까 수의 자리수가 1이라면 0으로 끝나는 오르막 수는 1개 (0), 수의 자리수가 2라면 1로 끝나는 오르막 수는 2개(수가 0으로 시작할 수 있댔으니가 00,01) 이런 씩입니다.

이렇게 쭉 나열해보면 규칙성이 보입니다.
위에 표기해둔 3자리수의 2로 끝나는 수(6) = 3자리수의 1로 끝나는 수(3) + 2자리수의 2로 끝나는 수(3)
라는 규칙성을 찾아볼 수 있습니다.

이걸 토대로 점화식을 세워보면

N자리수의 i로 끝나는 수 = N자리수의 i-1로 끝나는 수 + N-1자리수의 i로 끝나는 수

이런 형식일 겁니다.

DP느낌대로 1자리수는 죄다 초기 고정으로 박아두고, 2자리수부터는 위 점화식을 기반으로 풀이하면 될 것 같습니다.

---

코딩

dp = [[0]*10 for _ in range(1001)]
N = int(input())

자리수는 1001까지 나올 수 있다니까 0~9(끝나는 수) X 1001 짜리 이차원 리스트를 DP배열로써 제작해주겠습니다. 그리고 N자리수를 받습니다.

for i in range(10):
    dp[1][i] = 1

DP를 쓰기위한 초기 계산식 1자리수를 전부 1로 초기화해줍시다.

for i in range(2,N+1):
    for j in range(10):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

2자리수부터는, 0~9까지의 끝나는 수에 아까 세운 점화식 N자리수의 i로 끝나는 수 = N자리수의 i-1로 끝나는 수 + N-1자리수의 i로 끝나는 수 => dp[i][j] = dp[i-1][j] + dp[i][j-1]
을 넣어줍시다. 여기서 i는 자릿수, j는 끝나는 수라고 생각하시면 될 것 같습니다.

print(sum(dp[N])%10007)

마지막으로 N에 해당하는 배열 (0~9까지의 끝나는 수 기반 오르막 수의 개수들)의 합산을 10007로 나눈 값(문제 조건)을 출력하면 됩니다.

---

---