[백준-9184] 신나는 함수 실행 (Python)

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

---

[풀이]

 

- 문제에서 정의된 w함수를 그대로 구현해주었다. 하지만, 문제에 나온대로만 한다면 백트래킹이 아닌 그냥 재귀함수를 이용한 완전탐색이기 때문에 한 번 호출된 값을 3차원 리스트인 dp에 저장해주었다.

 

- dp리스트의 특정 값이 -1이면 즉, 아직 한번도 구해지지 않았다면 w함수를 호출하여 값을 구하여 저장해주었고 그렇지 않으면 dp리스트를 참조하여 w함수가 중복 실행되는 경우를 없앴다.

 

 

[깨달은 점]

 

- 맨 처음 풀이는 (0,0,0) ~ (20,20,20)까지 모두 dp에 저장한 후에 입력에 따라 값을 출력하도록 했는데, 예상보다 시간이 너무 오래걸렸다. 그래서 w 함수를 구현해보았는데 이는 더 오랜 시간이 걸렸다.

 

- 이유를 찾다보니.. 입력과 출력에서 많은 시간이 소요된 것 같다. 이전에는 input() 함수를 사용했는데 파이썬에서 input() 함수보다 stdin.readline()이 훨씬 빠르다고 한다.

 

- 문자열을 출력할 때에도 for문 맨 끝마다 print()함수를 쓰는 것보다 아래와 같이 result에 결과를 저장한 뒤 마지막 한 번 출력하는 것이 더 빠르다는 것도 알게 되었다.

 

- 솔직히 print를 여러 번 하는 것은 시간이 많이 차이나진 않지만, stdin.readline()과 input()과의 차이는 어마어마했다. input()을 사용했을 때는 1112ms였는데 stdin.readline()으로 바꾸니 112ms로 시간이 엄청나게 줄었다. 

 

from sys import stdin
dp=[[[-1 for _ in range(21)] for _ in range(21)] for _ in range(21)]
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 dp[20][20][20] if dp[20][20][20]!=-1 else w(20,20,20)
    dp[a][b][c]=0
    if a<b<c:
        dp[a][b][c]+=dp[a][b][c-1] if dp[a][b][c-1]!=-1 else w(a,b,c-1)
        dp[a][b][c]+=dp[a][b-1][c-1] if dp[a][b-1][c-1]!=-1 else w(a,b-1,c-1)
        dp[a][b][c]-=dp[a][b-1][c] if dp[a][b-1][c]!=-1 else w(a,b-1,c)
    else:
        dp[a][b][c]+=dp[a-1][b][c] if dp[a-1][b][c]!=-1 else w(a-1,b,c)
        dp[a][b][c]+=dp[a-1][b-1][c] if dp[a-1][b-1][c]!=-1 else w(a-1,b-1,c)
        dp[a][b][c]+=dp[a-1][b][c-1] if dp[a-1][b][c-1]!=-1 else w(a-1,b,c-1)
        dp[a][b][c]-=dp[a-1][b-1][c-1] if dp[a-1][b-1][c-1]!=-1 else w(a-1,b-1,c-1)

    return dp[a][b][c]
result=''
while(True):
    a,b,c=map(int, stdin.readline().split())
    if a==-1 and b==-1 and c==-1: break
    result+='w({}, {}, {}) = {}'.format(a,b,c,w(a,b,c)) + '\n'
print(result)