[BOJ] 2775번 부녀회장이 될테야(Python)

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이 주어진다

출력

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

제한

• 1 ≤ k, n ≤ 14

예제 입력

2
1
3
2
3

예제 출력

6
10

해설

“a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

도대체 아파트가 얼마나 크길래 이런 입주 조건이 있을까..? 값은 쌀까..?

이 문제는 브루트포스 방식으로 접근했다.  a층 b호수를 입력 받으면 0층부터 a층 b호수까지 모든 인원을 구하고 최종적으로 a층 b호수의 인원을 구하는 방식으로 문제를 풀었다.

T = int(input())

for t in range(T): #1
    k = int(input()) #2
    n = int(input()) #2
    l = [] #2
    cl = [] #2
    for i in range(k+1): #3
        for j in range(n): #4
            if i == 0: #5
                l.append(j+1) #5
            else:  #6
                d = sum(cl[:j+1]) #6
                l.append(d) #6
        cl = l # 7
        l=[] #7
    print(cl[-1]) #8

일단 이 문제는 테스트케이스를 입력 받기 때문에 

T = int(input())

T번 for문을 돌리고 그 안에서 코드랑 출력을 작성한다.

• section 1.

입력받은 테스트케이스로 반복문을 돌린다.

• section 2.

k = 층, n = 호수,  l  = 현재 층 인원에 대한 리스트, cl =이전 층 인원에 대한 리스트 변수명은 귀찮아서 그냥 맘대로 했다. 어차피 알고리즘 문제니까..

현재 층의 인원을 구해야 하기 위해서 이전층에 대한 인원 정보는 무조건 필요하기 때문에 cl을 선언했다

• section 3.

0부터 입력 받은 k까지 반복문을 돌리기 위해 range(k+1)로 for문을 돌린다.

• section 4.

n은 호수에 대한 for문

• section 5.

0층일때, 인원 수를 넣어준다. 호수 = 인원수

• section 6.

0층이 아닐때, cl에 j까지의 인원 수를 sum을 통해 총합한 수를 l에 append 해준다.

• section 7.

위에 for문으로 만들어진 l을 cl에 다시 할당하고 l을 다시 빈 리스트로 만들어준다.

• section 8.

최종적으로 cl에 마지막 요소를 출력한다.

예전에 푼 문제라 코드를 천천히 읽어보면서 리뷰했는데 보면서 개선해야할 부분이 많다고 생각했다.

특히 백준 다른 사람이 제출한 정보를 볼 수 있는데 위 처럼 실행시간 같은게 많이 차이가 나면 현타가 온다. 

이 문제는 나중에 다시 개선해보겠다!!