[BOJ] 백준 2775 부녀회장이 될테야 (Swift)

문제

풀이

이 문제는 다이나믹 프로그래밍 기법을 사용해서 쉽게 풀이할 수 있습니다.
먼저, 0층의 i호에는 i명이 산다. 라는 문제의 지문을 이용해서 0층, 1층, 2층... 바텀업 방식으로 답을 도출할 수 있다는 아이디어를 얻을 수 있습니다.

4호까지 있다고 가정하고 DP 테이블을 어떤식으로 채워나갈지 확인해보시죠..!

2층 3호는 어떤식으로 채워줘야 할까요??

2층 3호 = 1층 1호 + 1층 2호 + 1층 3호 일 것입니다.

n층 1호는 0층 1호가 1이기 때문에, 무조건 1이 될 수 밖에 없습니다.

1층 2호 = 0층 1호 + 0층 2호 겠죠??

하지만 이것은 1층 1호 + 0층 2호 라고 해도 되겠죠??

1층 3호는 어떨까요??

1층 3호 = 0층 1호 + 0층 2호 + 0층 3호 겠네요.

0층 1호 + 0층 2호 = 1층 2호

이기 때문에 1층 3호 = 1층 2호 + 0층 3호 가 되겠네요.

$y = 층, x = 호$
$초기값: f(0,x) = x, f(y, 1) = 1$
$f(y, x) = f(y, x - 1) + f(y - 1, x)$
의 점화식이 성립하게 됩니다!

이제 총 14층 14호까지의 dp 테이블을 채워주기만 하고 출력해주면 되겠네요!

소스코드

후기

0층부터 차근차근 채워보면서 규칙을 찾고, 초기 값과 점화식을 세우기만 하면 쉽게 풀 수 있는 문제인 것 같습니다.