[파이썬/Python] 백준 2775번 부녀회장이 될테야

[파이썬/Python] 백준 2775번 부녀회장이 될테야

2775번: 부녀회장이 될테야

---

문제

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

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

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

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

제한

• 1 ≤ k, n ≤ 14

예제 입력

2
1
3
2
3

예제 출력

6
10

풀이 1

2차원 리스트

import sys
input = sys.stdin.readline

t = int(input())  # 테스트 케이스의 수 입력

for _ in range(t):
    k = int(input())  # 층 수 입력
    n = int(input())  # 호 수 입력
    lst = [[i for i in range(1, 15)] for _ in range(k+1)]  # 초기 아파트 거주민 수 리스트 생성
    i = 1  # 층 수 변수 초기화
    j = 0  # 호 수 변수 초기화
    
    while True:
        j += 1  # 다음 호로 이동
        
        # 현재 호의 거주민 수를 이전 층의 1호부터 현재 호까지의 거주민 수의 합으로 업데이트
        lst[i][j-1] = sum(lst[i-1][:j])
        
        if i == k and j == n:  # 입력한 층과 호에 도달한 경우
            print(lst[i][j-1])  # 거주민 수 출력
            break
        
        if j == 14:  # 현재 층의 마지막 호까지 도달한 경우
            i += 1  # 다음 층으로 이동
            j = 0  # 첫 번째 호로 초기화

풀이 2

1차원 리스트

from sys import stdin

t = int(stdin.readline())  # 테스트 케이스의 수 입력
cnt = 0

while cnt < t:
    k = int(stdin.readline())  # 층 수 입력
    n = int(stdin.readline())  # 호 수 입력
    array = [t for t in range(1, n+1)]  # 초기 거주민 수 리스트 생성

    # 각 층마다 거주민 수를 업데이트
    for i in range(k):
        for j in range(1, n):
            array[j] += array[j-1]
    
    print(array[-1])  # 마지막 호의 거주민 수 출력
    cnt += 1

두 문제의 알고리즘과 시간 복잡도를 비교해보자.

첫 번째 코드의 알고리즘:
입력으로 주어지는 층 수와 호 수에 대해 2차원 리스트를 생성하고 초기화한다.
각 호마다 이전 층의 1호부터 현재 호까지의 거주민 수의 합을 계산하여 현재 호의 거주민 수로 업데이트한다.
입력받은 층과 호에 도달하면 해당 호의 거주민 수를 출력한다.

 

두 번째 코드의 알고리즘:
입력으로 주어지는 층 수와 호 수에 대해 거주민 수를 저장하는 리스트를 생성하고 초기화한다.
각 층마다 거주민 수를 업데이트한다. 현재 호의 거주민 수는 이전 호의 거주민 수와 그 이전 호들의 거주민 수의 합으로 계산된다.
마지막 호의 거주민 수를 출력한다.

 

알고리즘의 차이:
첫 번째 코드는 2차원 리스트를 사용하여 층과 호에 대한 거주민 수를 계산한다. 각 호의 거주민 수는 이전 층의 일부 거주민 수를 합산하여 계산된다.
두 번째 코드는 1차원 리스트를 사용하여 각 층마다 거주민 수를 계산한다. 각 층의 거주민 수는 이전 층의 거주민 수와 그 이전 호들의 거주민 수를 합산하여 계산된다.

 

시간 복잡도 비교:
첫 번째 코드에서는 k층 n호까지 거주민 수를 계산하기 위해 2중 반복문이 사용된다. 따라서 시간 복잡도는 O(kn)이다.
두 번째 코드에서는 k층 n호까지 거주민 수를 계산하기 위해 2중 반복문이 사용된다. 따라서 시간 복잡도도 O(kn)이다.
두 코드의 알고리즘과 시간 복잡도는 동일하며, 입력 크기에 따라 선형적으로 실행 시간이 증가한다.

 

시간복잡도는 동일하게 측정되지만, k 값이 높을 수록, n 값이 낮을 수록 수행 시간은 크게 차이날 것이다. 첫번째 코드는 층별로 모든 호수의 인원수를 계산해줘야하는 반면, 두번째 코드는 구하고자 하는 호수까지만 계산하면 된다. 문제를 보고 어디까지만 계산해도 되는지 생각을 잘 하신 것 같다.

 

참고자료

로그인