[백준] 9184번 : 신나는 함수 실행 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

9184번: 신나는 함수 실행

 

1. 문제 설명

2. 풀이과정

해당 문제는 -50부터 50까지 범위에서 3개의 수를 입력받아 w(a, b, c)의 값을 출력하는 문제이다.

문제에 나와있는 함수를 사용하면 재귀를 활용해 해당 값을 계산하므로 값에 따라 많은 시간이 소요될 수 있다.

하여 이미 구한 값을 저장하고 그 값을 사용하는 DP 알고리즘을 활용해 문제를 해결하고자 했다.

또한 해당 문제는 -50부터 50까지의 범위의 수를 입력받을 수 있는데 3개의 수 중 하나라도 0 이하이면 해당 결과는 1이므로 0부터, 3개의 수 중 하나라도 20을 넘으면 해당 결과는 w(20, 20, 20)의 결과이므로 20까지만 구하면 된다.

하여 a, b, c의 값에 따른 결과이므로 3차원 배열을 만들고 각 인덱스의 값은 0~20을 가지도록 한다.

해당 문제에서 주어진 함수를 응용하는데, 해당 값을 계산하여 반환하는 것이 아니라 3차원 배열에 저장하고 저장한 값을 반환하도록 수정한다.또한 해당 위치의 값이 0이 아닌 다른 값으로 이미 존재한다면 해당 값을 그대로 반환해 주도록 추가한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 문제에서 정의된 함수를 새롭게 정의한다. def w(a, b, c)
3. 만약 a, b, c 중 하나라도 0 이하이면 if (a <= 0 or b <= 0 or c <= 0)
4. 1을 반환한다. return 1
5. 만약 a, b, c 중 하나라도 20을 넘으면 if (a > 20 or b > 20 or c > 20)
6. 20, 20, 20을 인수로 하여 다시 함수를 호출한다. return w(20, 20, 20)
7. 만약 해당 위치의 값이 0이 아니면 해당 위치의 값을 반환한다. if (W[a][b][c]): return W[a][b][c]
8. 만약 a < b 이고 b < c 이면 if (a < b and b < c)
9. 해당 위치의 값은 문제에 나와있는 값으로 저장한다. W[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
10. 저장한 해당 위치의 값을 반환한다. return W[a][b][c]
11. 나머지의 경우에는 해당 위치의 값을 문제에 나와있는 값으로 저장한다. W[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)
12. 저장한 해당 위치의 값을 반환한다. return W[a][b][c]
13. 0부터 20까지 인덱스를 가지도록 3차원 배열을 생성한다. W = list(list(list(0 for _ in range(21)) for _ in range(21)) for _ in range(21))
14. -1, -1, -1을 입력받을 때까지 반복해야 하므로 무한 반복문을 활용한다. while (True)
15. a, b, c 각 수를 입력받는다. a, b, c = map(int, sys.stdin.readline().split())
16. 만약 모든 수가 -1이면 종료한다. if (a == -1 and b == -1 and c == -1): break
17. 그게 아니라면 해당 값을 계산하여 출력한다. print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

반응형

3. 소스코드

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

    W[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 W[a][b][c]

W = list(list(list(0 for _ in range(21)) for _ in range(21)) for _ 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(f"w({a}, {b}, {c}) = {w(a, b, c)}")