부녀회장이 될테야
https://www.acmicpc.net/problem/2775
처음엔 재귀함수로 문제를 해결하려고 했다.
1
2
3
4
5
6
7
8
9
10
11
12
|
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))
|
cs |
재귀함수는 자기 자신을 호출하는 함수를 말한다. 그런데 이렇게 코드를 작성해서 실행해보니 시간초과가 나왔다. 1초의 시간제한보다 더 긴 시간이 필요한 것이다.
그래서 어떻게 해결해야되나 고민하다가 아파트 각 호실에 사는 사람들의 수를 처음에 구해두고 입력받은 호실의 사람수를 찾아서 출력하려고 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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])
|
cs |
apartment라는 list는 다음과 같다.
그런다음 apartment[k][n-1]로 입력받은 숫자에 대응하는 사람수를 화면에 출력한다
이 방법은 k와 n의 수가 적을 땐 비효율적인 방법이다. 굳이 14층 14호까지 구할 필요가 없기 때문이다.
하지만 위의 재귀함수를 사용하는 경우보다는 훨씬 빨리 고층의 경우를 구할 수 있다.
실제로 counter를 이용해 재귀함수가 호출된 횟수를 구해보았다.
k와 n의 값이 커질수록 호출 횟수가 기하급수적으로 커진다.
두 번째 경우는 각 호실별로 sum을 한 번씩 하는것이므로 14*14 = 196번만 sum을 실행해도 값을 구할 수 있다.
이것보다 더 시간을 단축하려면 원하는 k층 n호실까지만 값을 구하는 것이다.
1
2
3
4
5
6
7
8
9
10
11
|
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])
|
cs |
큰 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 를 생성 후 이를 사용하면, 해당 함수가 몇번 실행되었는지를 외부에서도 확인 가능하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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=}")
|
cs |
이번 문제를 풀 때 매번 더해서 구하는 것 보다 한 번에 계산할 수 있는 규칙이 있나 고민하다가 시간이 많이 갔다.
규칙이 필요할 때도 있지만 더하는 과정을 더 간단하게 만드는 것이 도움이 될 때도 있다.
참고한 페이지
https://yongbeomkim.github.io/python/python-count/
'알고리즘' 카테고리의 다른 글
백준 - 1978번 / 소수 (0) | 2021.08.04 |
---|---|
백준 - 1011번 (0) | 2021.08.03 |
백준 - 10250번 (0) | 2021.08.03 |
백준 - 2869번 (0) | 2021.08.03 |
백준 - 1316번 (0) | 2021.08.03 |