백준 2775번- '부녀회장이 될테야' (PYTHON 풀이)

문제:

 

처음에 이 문제에서 헷갈리는 부분이 있었는데 핵심 내용은 '아래층의 1호부터 b호까지 사람들 수의 합만큼'이다.

문제를 잘 안 읽었을 때는 i호엔 i명이라고 했으니까 3호면 3명, 4호면 4명인가 싶었다가 예제 출력이 맞질 않아서 다시 읽고 서치도 해봤다.

어쨌든 결과적으로는 다음과 같다. 위 굵은 글씨를 생각하면서 아래 내용을 보면 이해가 될 것이다.

층	1호	2호	3호
0층	1	2	3

 

처음 0층은 위와 같다. 0층이 시작이니까 0-1층은 없으니 위와 같이 시작될 것이다.

층	계산식	결과
1층 1호	0층(1호)	1
1층 2호	0층(1호+2호)	3
1층 3호	0층(1호+2호+3호)	6

 

1층으로 올라가게되면 이제 1-1층인 0층의 값이 있기 때문에 0층의 1호부터 각 호수에 맞는 사람의 합이 계산이 된다.

1층 1호는 1-1층인 0층의 1호값인 1이 들어가게 될 것이고 1층 2호는 0층 1~2호의 누적값인 3, 그 다음 호수는 6이 들어간다.

이렇게 층의 호수가 늘어날 때마다 이전층의 호수의 누적값이 들어간다는 것이 핵심이다!

 

풀이:

T = int(input())

for i in range(T):
    k = int(input())
    n = int(input())

    floor = []
    for j in range(1, n+1):
        floor.append(j)
    
    for q in range(k):
        new = []
        total = 0
        for e in floor:
            total += e
            new.append(total)
        floor = new
    
    print(floor[-1])

정답 코드는 다음과 같다.

우선 정답을 구할 케이스 수를 입력받고 해당 수만큼 for문을 돈다.

첫번째 케이스에서 층과 호수를 입력받고 0층에 해당하는 수를 저장하기 위한 floor를 선언한다. 그 다음 호수만큼 for문을 돌면서 floor에 최초 인원수를 저장해준다. 

그 다음 for문에서는 층에 대한 수를 돌면서 새로운 리스트인 new와 누적합을 더해줄 total을 선언해준다. 안쪽 for문도 새로 만들어서 최초 0층에 대한 수가 저장되어 있는 floor의 값을 돌면서 누적합으로 계산해주고 이 값을 새로운 리스트인 new에 추가해준다. 이렇게 첫번째 for문이 돌면 floor에는 1층값이 계산되어있을 것이다. (new값을 넣어줬으니) 

이러한 순서대로 전부 for문을 돌면 리스트의 마지막값엔 마지막 호수의 누적값이 있을 것이니 -1 인덱스를 출력해주면 문제를 풀 수 있다.