Problem
https://www.acmicpc.net/problem/2775
Solution
오답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def people(k, n):
count = 0
if k==0:
return n
else:
for i in range(1,n+1):
count += people(k-1, i)
return count
t = int(input())
for i in range(t):
k = int(input())
n = int(input())
print(people(k, n))
재귀함수 형태로 함수를 정의해서 제출하니 시간초과로 오답처리가 됐다. 낮은 층수를 구할때는 큰 문제가 없지만 14층 14호와 같이 높은 층을 구하려면 시간이 오래 걸리게 되어 다른 방법을 찾게 됐다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
apart_list = [[0 for j in range(14)] for i in range(15)]
for i in range(15):
apart_list[i][0] = 1
for h in range(14):
apart_list[0][h] = h+1
for i in range(1,15):
for j in range(1,14):
apart_list[i][j] = apart_list[i][j - 1] + apart_list[i - 1][j]
t = int(input())
for i in range(t):
k = int(input())
n = int(input())
print(apart_list[k][n-1])
Memo
위 코드는 한 칸의 값은 바로 왼쪽과 아래쪽 값의 합과 같다는 점을 활용하여 2차원 리스트를 만들어 문제를 해결하였다.