a층 b호에는 a-1층의 1~b호까지의 사랍 수의 합만큼의 사람이 산다.
0층 i호는 i명이 살고, 호수는 1부터 시작한다.
k는 층수, n은 호수
2층은 1층의 사람수를 다 알아야하고, 3층은 2층의 사람의 수를 알아야하기 때문에 직접 계산할 수 밖에 없다고 생각했다.
DP 사용
아파트 0층을 먼저 채워준다.
apt = [[_ for _ in range(1, n + 1)]]
그 전층의 합을 슬라이스[:]
를 사용해서 더해준다.
for
: O(n2)sum
: O(n)O(n3)
DP나 재귀 모두 시간이 오래 걸림 O(n3)
숏코딩 코드를 참고해서 조합의 성질을 이용해서 풀면 단순하다는 것을 알았다.
현재 코드 : 68ms
조합 사용 : 84ms
import math
..
print(math.comb(k+n, n-1))
조합의 성질 중 파스칼의 삼각형에서 하키스틱 패턴이라는 것이 있다. 이를 이용한 풀이인데 설명을 하자면
파스칼의 삼각형에서 위 두 수의 합은 아래의 수이다.
이를 combination으로 나타낼 수 있는데 아래와 같다.
nCk = n-1Ck-1 + n-1Ck
여기서 하키스틱 패턴이란
오른쪽 아래 대각선 방향의 총 합이 그 왼쪽 값과 같다는 것이다.
이를 활용해서
k+nCn-1
이 식을 통해 k층 n호의 사람수를 계산하는 것이다.
난이도 | 정답률(%) |
---|---|
브론즈2 | 57.364% |