백준 - 2775번 / 함수의 호출 횟수(counter)

부녀회장이 될테야

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

2775번: 부녀회장이 될테야

처음엔 재귀함수로 문제를 해결하려고 했다.

def resident(k, n):
    if k == 0:
        return n
    total = 0
    for i in range(1, n+1):
        total += resident(k-1, i)
    return total
T = int(input())
for _ in range(T):
    k = int(input())
    n = int(input())
    print(resident(k, n))

 

재귀함수는 자기 자신을 호출하는 함수를 말한다. 그런데 이렇게 코드를 작성해서 실행해보니 시간초과가 나왔다. 1초의 시간제한보다 더 긴 시간이 필요한 것이다.

그래서 어떻게 해결해야되나 고민하다가 아파트 각 호실에 사는 사람들의 수를 처음에 구해두고 입력받은 호실의 사람수를 찾아서 출력하려고 했다.

 

apartment = []
for i in range(15):
    floor = []
    if i == 0:
        for k in range(1, 15):
            floor.append(k)
    else:
        for k in range(14):
            floor.append(sum(apartment[i-1][:k+1]))
    apartment.append(floor)
N = int(input())
for _ in range(N):
    k = int(input())
    n = int(input())
    print(apartment[k][n-1])

apartment라는 list는 다음과 같다.

그런다음 apartment[k][n-1]로 입력받은 숫자에 대응하는 사람수를 화면에 출력한다

이 방법은 k와 n의 수가 적을 땐 비효율적인 방법이다. 굳이 14층 14호까지 구할 필요가 없기 때문이다.

하지만 위의 재귀함수를 사용하는 경우보다는 훨씬 빨리 고층의 경우를 구할 수 있다.

 

실제로 counter를 이용해 재귀함수가 호출된 횟수를 구해보았다.

k와 n의 값이 커질수록 호출 횟수가 기하급수적으로 커진다.

두 번째 경우는 각 호실별로 sum을 한 번씩 하는것이므로 14*14 = 196번만 sum을 실행해도 값을 구할 수 있다.

 

이것보다 더 시간을 단축하려면 원하는 k층 n호실까지만 값을 구하는 것이다.

T = int(input())
for i in range(T):
    k = int(input())
    n = int(input())
    s = []
    for j in range(1, n+1):
        s.append(j)
    for p in range(k): # 층수
        for o in range(1, n): # 호수
            s[o] += s[o-1]
    print(s[-1])

큰 list를 생성할 필요도 없다. 

0층에 사는 사람의 수를 s라는 list안에 입력한다. 0호는 생각하지 않으며, 1호에 1명부터 시작하므로 range(1, n+1)만큼 넣어준다.

k층의 값을 구하기 위해 for문을 k번 실행한다.

s[o] = s[o] + s[o-1]인데 range(1, n)이므로 맨 처음 s[1](2호실)부터 계산하기 시작한다.

T = 1, k = 3, n = 3인 경우 s는 다음과 같이 변한다.

0층인 [1, 2, 3]부터 생성되고 s[1](102호)의 값을 구하고, s[2](103호)의 값을 구한다.

모든 호수의 값을 구할 필요가 없으므로 각 층별 list를 남겨둘 필요가 없고 s의 값을 바꿔가면서 계산할 수 있다.

 

* 함수의 호출 횟수 구하는 방법

함수의 이름과 동일한 객체 method 를 생성 후 이를 사용하면, 해당 함수가 몇번 실행되었는지를 외부에서도 확인 가능하다.

def resident(k, n):
    resident.counter += 1
#     if k == 0:
#         return n
#     total = 0
#     for i in range(1, n+1):
#         total += resident(k-1, i)
#     return total
# T = int(input())
resident.counter = 0
for _ in range(T):
#     k = int(input())
#     n = int(input())
#     print(resident(k, n))
    print(f"{resident.counter=}")

 

이번 문제를 풀 때 매번 더해서 구하는 것 보다 한 번에 계산할 수 있는 규칙이 있나 고민하다가 시간이 많이 갔다.

규칙이 필요할 때도 있지만 더하는 과정을 더 간단하게 만드는 것이 도움이 될 때도 있다.

 

 

참고한 페이지

https://yongbeomkim.github.io/python/python-count/

Python 함수실행 횟수 계산하기