[백준-파이썬] 2775번 문제. 부녀회장이 될테야 (브론즈1)

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

 

case = int(input())

for _ in range(case):
    k = int(input())
    n = int(input())
    
    # 0층 인원수 배열 만들기
    arr = [level for level in range(1, n+1)]
    
    # K층까지 돌고
    for i in range(k):
    
    	# 각층의 n호까지 돌기
        for j in range(1, n):
        
            # 모든 층의 1호[인덱스0]에는 1명이 살고 있으므로 arr[0]은 필요 X
            arr[j] += arr[j-1]

	# 마지막 호실 인원 출력
    print(arr[-1])

 

케이스 수는 다시 사용되지 않으므로 변수를 할당해줄 필요가 없습니다. 그래서 for _ in ~ 으로 작성합니다.

그리고 0층은 i호에는 i명이 산다고 합니다. 1호부터 있다고 했으니 1호에 1명, 2호에 2명... 이런식이겠군요.

 

0층 = [1, 2, 3, ...]

 

그래서 0층을 미리 만들어둡니다.

 

    arr = [level for level in range(1, n+1)]

 

이렇게 arr안에서 반복문을 써서 자동으로 배열을 만드는 방법이 있습니다.

이걸 list comprehension이라고 부릅니다.

 

k층까지 돌고, 각 층마다 n호까지만 돌면 됩니다.

 

각 호실 n호에는 한층 아래의 1~n호 까지의 인원이 있다고 합니다.

표로 그려보면 아래와 같습니다.

1층 3호실이라면,

0층의 1호~3호실까지를 더한 6명이 있습니다.

 

 

2층의 4호실이라면,

1층의 1~4호실까지를 더한 20명이 있습니다.

 

그림에서 보다시피 모든 층의 1호실은 1명이 살게 되기 때문에 계산에서 제외합니다.

1호실들은 바로 아래층의 1호실의 인원수만 가져오게 되기 때문입니다.

 

어떻게 이런 표가 나왔을까요?

 

이 부분을 처리하는 코드를 보겠습니다.

 

        # 모든 층의 1호[인덱스0]에는 1명이 살고 있으므로 arr[0]은 필요 X
        arr[j] += arr[j-1]

 

어떻게 이 한줄로 마법같이 해결되는 걸까요.   :)

 

위 식을 돌리면 처음엔 arr[1] += arr[0] 이 됩니다.

 

(3층 4호실 인원수를 구한다고 가정하겠습니다.)

 

1층의 2호실 인원수를 구한다고 가정할 때, 현재 arr은 0층 기본값인 [1 , 2, 3, 4]입니다. 

1호실은 앞에서 말했듯 제외하고 2호실부터 계산합니다.

 

arr[1]은 2 입니다. arr[0]은 1입니다. 2+1 = 3 이 됩니다. 이 값을 arr[1]에 다시 넣어줍니다.

이렇게 해서 3이 저장됩니다.

 

현재 arr의 상태는 아래처럼 어정쩡한 상태입니다.

 

arr = [1, 3, 3, 4] 

 

 

1, 3, 은 1층의 숫자로 업데이트 된 상태이고

3, 4는 아직 0층의 숫자입니다.

 

 

 

다음 호실도 돌아볼까요.

arr[2] = 3, arr[1] = 3입니다. 3+3 = 6 이 됩니다. 이 값을 arr[2]에 다시 넣어줍니다. 코드를 다시 볼까요.

 

        # 모든 층의 1호[인덱스0]에는 1명이 살고 있으므로 arr[0]은 필요 X
        arr[j] += arr[j-1]

 

이렇게 해서 6이 저장됩니다.

<현재 배열 상태>

arr = [1, 3, 6, 4] 

 

 

마지막.

arr[3] = 4, arr[2] = 6, 4 + 6 = 10

10이 담기게 됩니다.

 

arr = [1, 3, 6, 10] 

 

드디어 배열이 1층의 인원수로 모두 업데이트가 되었습니다.

 

 

이제 이 1층 배열을 가지고 2층으로 계산하러 올라가는 거죠.

 

이렇게 위층들도 돌고 나면 아래처럼 표가 완성됩니다.

 

 

3층 4호실은 35명이 살고 있군요. 복작복작하겠습니다.

 

이때의 arr는 당연히 [1, 5, 15, 35] 일테니 arr[-1]을 출력하면 통과되겠습니다.

 

    # 마지막 호실 인원 출력
    print(arr[-1])

 

 

 

 

 

 

이제 숏코드를 구경해볼까용.

 

import math
i=input
for n in[int]*int(i()):k=n(i());print(math.comb(k+n(i()),k+1))

 

역시 숏코드 상위권을 차지하시는 분들은 괴물들인가 봅니다. 뭐가 뭔지 감도 안옵니다......

나중에 분석해보겠습니다. ^^;