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

• 문제

---

---

 

• 잘못된 풀이

문제를 보자마자 recursive(재귀) 알고리즘이 생각났다.

Recursive로 풀어보고자 했는데, 실패했다. 

 

• 올바른 풀이

T = int(input())

for i in range(T):
    k = int(input()) # 층
    n = int(input()) # 호
    floor_0 = [i for i in range(1, n+1)] # 0층 사람 수

    for j in range(k):
        for p in range(1, n):
            floor_0[p] += floor_0[p-1]
    print(floor_0[-1]) # 0번 인덱스부터 시작하기 때문에 -1

 

Recursive가 아닌 풀이 방법을 모색했다. 

0층을 기준으로 1호는 1명, 2호는 2명, 3호는 3명 ... i호는 i명의 사람이 있음을 나타내는 floor_0 list를 만들었다.

 

그리고 0층부터 차근히 사람 수를 구하는 알고리즘을 생각했다. 

3층: 1 5 15 35 70 ... 1+5+ ... +(1+3+...+(1+2+...+n))
2층: 1 4 10 20 35 ... 1+3+ ... +(1+2+...+n)
1층: 1 3 6 10 15 ... 1+2+...+n
0층: 1 2 3 4 5  ... n

 

1층 1호 = 0층 1호

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

1층 3호 = 1층 1호 + 1층 2호 + 1층 3호

 

이런식으로 현재 호수는 이전 호수를 모두 더한 값이므로,

이중 for문을 통해 현재 호수를 기준으로 이전 호수를 모두 더해주었다.