[백준/BOJ/2775] 부녀회장이 될테야

movie·2021년 10월 11일
0
post-thumbnail

2775 | 부녀회장이 될테야


문제 접근 & 설계

  1. a층 b호에는 a-1층의 1~b호까지의 사랍 수의 합만큼의 사람이 산다.

  2. 0층 i호는 i명이 살고, 호수는 1부터 시작한다.

  3. k는 층수, n은 호수


  • 2층은 1층의 사람수를 다 알아야하고, 3층은 2층의 사람의 수를 알아야하기 때문에 직접 계산할 수 밖에 없다고 생각했다.

  • DP 사용


  1. 아파트 0층을 먼저 채워준다.

    • apt = [[_ for _ in range(1, n + 1)]]
  2. 그 전층의 합을 슬라이스[:]를 사용해서 더해준다.


사용한 스킬



시간 복잡도

  • 테스트케이스 반복문 제외
  • 중첩 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호의 사람수를 계산하는 것이다.


난이도


난이도정답률(%)
브론즈257.364%

알고리즘 분류


  • 수학
  • DP

소스코드 📃

profile
영화보관소는 영화관 😎

0개의 댓글