[python]2775.부녀회장이 될테야

부녀회장이 되고싶단다. 소원을 들어주자.

그 아파트에는 "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항이 있다고 한다. 별.. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하는 프로그램을 만드는 문제이다.

 

재귀함수를 이용하여 풀 수 있지만 재귀를 생각하기 귀찮아서 다른 방법을 생각했다. 

0층 3호까지 거주인의 수를 리스트로 나타내면 [1, 2, 3]이다.

1층 3호까지의 거주인 수를 리스트로 나타내면[1, 1+2, 1+2+3]

2층 3호까지는 그럼 [1, 1+1+2, 1+1+2+1+2+3]

3층 3호까지는 [1, 1+1+1+2, 1+1+1+2+1+1+2+1+2+3]

규칙이 있는 것을 알 수 있는데 k층의 n호= k층의 (n-1)호의 거주인들 수 + (k-1)층의 n호 거주인들 수라는 것을 알 수 있다. (1호는 층에 상관없이 항상 1명만 거주하므로 1호 제외)

이를 이용하여 코드를 짜면

 

for _ in range(int(input())): #케이스
    k=int(input()); n=int(input())
    list=[i for i in range(1,n+1)] #0층
    for a in range(k): #k번
        for j in range(1,n): #n-1번; (index 0은 항상 1이므로 제외)
            list[j]=list[j]+list[j-1] #갱신
    print(list[n-1]) 

n호는 리스트상 인덱스 n-1이다.

 

www.acmicpc.net/problem/2775