(Python/🥉1)백준 알고리즘 2775번: 부녀회장이 될테야

문제 출처:https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

풀이:

n = int(input())                          # 테스트케이스 갯수
for i in range(n):
    k = int(input())                      #층수
    n = int(input())                      #호수
    result = [i for i in range(1,n+1)]    # for문 값을 변수 i 에다가 담음
    for j in range(k):                     
        for x in range(1,n):              
            result[x] += result[x-1]      # j = 1일때 result[1] = 1   [2] = 3 [3] = 6
    print(result[n-1])                    # j = 2일때 result[1] = 1   [2] = 4 [3] = 10
                                          # j = 3일때 result[1] = 1   [2] = 5 [3] = 15

지금까지 푼 문제중에 제일 어려운 문제인거같다.

 

규칙은 같은층전호수 + 층-1 같은호수 합이다.

식으로 쓰면

 

result = [i for i in range(1,n+1)]   
    for j in range(k):                
        for x in range(1,n):           
            result[x] += result[x-1]   
    print(result[n-1])

쉽게 생각했을때 j는 층수이다 그래서

j가 1면 result 는 [1, 3, 6] 출력된다

근데 j가 2층이면

201호는 result[1,0] 두개를 더하므로 1이고 

202호면 result[2,1]을 더해야해서 result[1]은 위에서 3이고 result[0]은 1이므로 3+1 은 4 이런식으로 진행되고 

이걸 다시 result[2]에 담는다

 

>> j가 2면 result 는 [1,4,10] 출력