백준 2775번 파이썬 풀이: 부녀회장이 될테야

백준 2775번 부녀회장이 될테야

 

알고리즘 분류: 수학, 조합론

 

링크: https://www.acmicpc.net/problem/2775

 

2775번: 부녀회장이 될테야

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

 

 

문제 파악

 

처음에 이 문제를 잘 이해하지 못했었는데 쉽게 예를들어 설명을 하자면

 

3층 4호에 살려면 2층 1, 2, 3, 4호에 사는 사람들의 수의 합만큼 사람들을 데려와 살아야한다.

 

0층의 i호에는 i명이 살기 때문에 이를 이런식으로 나타낼 수 있다.

 

3층 : 1 5 15 35

2층 : 1 4 10 20

1층 : 1 3 6 10

0층 : 1 2 3 4

 

 

코드

 

처음에 재귀를 이용해서 풀어보려고 했으나 실패하였다.

 

백준 문제의 특성상 파이썬으로 재귀를 통해 풀려고하면 시간초과나 안되는 경우가 많다.

(워낙 큰 수를 대입하기 때문에)

 

틀린 풀이지만 설명을 해보자면 k층 n호에 살려면 k-1층의 1부터 n호까지의 사람수를 합해야한다.

 

people이라는 변수에 k-1층의 1부터 n호까지의 사람수를 전부 더해주고 리턴한다.

 

그러나 시간 초과로 인해 이 방식으로는 풀지 못하고 반복문을 사용해야 할 것 같다.

 

이제 정답 풀이를 보자면

 

people이라는 변수에 0층에서 1부터 n호까지의 각각 사람수를 리스트에 담아두었다.

 

for 문을 이중으로 반복하면서 people안에 있는 인덱스들을

 

people[y] += people[y-1]로 바꿔주는데 그냥 글로만 봐서는 이해가 잘 가지 않는다.

 

이게 어떤식으로 변하는지 12번줄 바로밑에 print(people)을 넣어주면 이해가 된다.

 

앞서 예를 들었던 3층 4호에 살고 싶을 때 거주민 수를 출력하는 것이다.

 

맨 윗줄은 처음 0층 i호에 사는 거주민 수를 리스트에 담아둔 것이고

 

이를 반복문을 통해서 층이 바뀌면 i호에 사는 사람들도 늘어나는 것을 차근차근 바꿔주는것이다.

 

마지막으로 반복문이 끝나면 k층 n호까지 사는 거주민들이 리스트에 담겨져있으니

 

마지막 인덱스를 출력하면 k층 n호에 사는데 필요한 거주민 수를 출력할 수 있다.