[BOJ/Step15] 9184 : 신나는 함수 실행 (Python)

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

---

이게 대체 어떻게 풀어야 되는 건지 점화식을 찾아서 어떻게 해야되는건가

w(20, 20, 20) 부터 하나하나 손으로 풀어쓰는데 아무리 심해도 대체 이딴 문제일리가 없겠다 싶어서 구글링..

 

했더니 메모이제이션? 이라는 게 나오는데 세상에 ko.wikipedia.org/wiki/메모이제이션

약간 혁명이었음 뇌 깨끗해지는 느낌.?

 

1. a, b, c범위가 하나라도 0 이하이면 1을 반환하고 하나라도 20 이상이면 w(20, 20, 20)을 호출하기 때문에 최대 범위는 20

  1-1. ww[20][20][20]까지의 리스트를 생성한다

2. a, b, c를 입력받아 셋 다 -1이면 while문을 탈출

3. w(a, b, c) 호출

  3-1. a, b, c 의 범위 확인 (0 <= a, b, c <= 20)

  3-2. ww[a][b][c] 값 확인. 0이 아닐때만 반환

  3-3. a < b < c 이면 w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) 반환 => 재귀

  3-4. 위 어디에도 속하지 않으면 w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 반환 => 재귀

 

미리 리스트를 생성하고 값을 넣는다..

3-2번이 진짜 와 대박임 어떻게 이런 생각을 ㅋㅋㅋㅋㅋ... 난 아직 멀었다

 

# 9184.py

ww = [[[0] * 21 for _ in range(21)] for __ in range(21)]


def w(x, y, z):
    if x <= 0 or y <= 0 or z <= 0:
        return 1
    if x > 20 or y > 20 or z > 20:
        return w(20, 20, 20)
    if ww[x][y][z]:
        return ww[x][y][z]
    if x < y < z:
        ww[x][y][z] = w(x, y, z-1) + w(x, y-1, z-1) - w(x, y-1, z)
        return ww[x][y][z]
    ww[x][y][z] = w(x-1, y, z) + w(x-1, y-1, z) + w(x-1, y, z-1) - w(x-1, y-1, z-1)
    return ww[x][y][z]


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

    print(f'w({a}, {b}, {c}) = {w(a, b, c)}')

 

근데 놀라운 사실
그냥 숫자 세개만 입력받는거라 큰 차이 없을줄 알았는데
input()함수 쓰는거랑 readline()함수 쓰는거랑 차이 엄청나다..

물론 readline()이 열배 빠르다 ㅎ