BOJ 2775 : 부녀회장이 될테야

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

풀이

import sys

def data_sum(data_list, n):
    floor_d_list = []
    for j in range(1, n+1):
        floor_d_list.append(sum(data_list[:j]))
    
    return floor_d_list

if __name__ == '__main__':
    num = int(sys.stdin.readline())

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

        sum_d = []        
        for j in range(1,n+1):
            sum_d.append(j)
        
        floor_d = []
        floor_d.append(sum_d)
        for floor in range(k):
            floor_d.append(data_sum(floor_d[floor], n))

        print(floor_d[k][n-1])

이 문제는 누적 합(Prefix sum, Cumulative sum)이라 하는 문제를 살짝 응용했다. (https://sskl660.tistory.com/77)

[Java]누적 합(Prefix Sum , Cumulative Sum)

문제가 생각보다 쉽지는 않았다. 개인적으로 지금 solved.ac 실버 5 수준에서 1시간 가량 걸린 내용 같다...(https://solved.ac/profile/jhchae92)

solved.ac

 

---

1. 먼저 a-1 층의 배열 중 최하위는 0층 이므로, 0층(a_0)의 수열은 k는 (k = 1,2,3...) 이다. 이것을 먼저 베이스로 세팅한다.
2. 다음 층의 배열은 a_1 인데 이는 a_0부터 해당 호수까지 k의 누적합을 계산한 것 이다.
3. 이 순으로 a-1층인 a_k배열까지 2를 반복하면 해당 층, 호수 까지의 누적 합 행렬의 전체 배열을 얻을 수 있고,
4. 그 층의 호수에 필요한 인원 수를 빼올 수 있다.