2775: 부녀회장이 될테야 - Python

beaver.zip·2024년 12월 5일

백준

[알고리즘] 백준

목록 보기

15/45

문제

https://www.acmicpc.net/problem/2775

k층 n호의 인원 수를 구할 때,

풀이 1: k-1층의 1호부터 n호까지의 인원 수의 합을 구함.
풀이 2: k-1층의 n호와 k층의 n-1호의 인원 수의 합을 구함.

풀이 1

import copy

def apt(k, n): 
    prev = [i for i in range(1, n+1)] # 이전 층을 저장 - 초기값: [1, 2, 3, ... , n]
    next = [1] * n # 다음 층을 저장 - 초기값: [1, 1, ..., 1] (모든 층의 1호는 1이고, 2호부터는 대입받을 예정)

    for _ in range(k): # k번 반복
        for j in range(1, n): # 2호부터 n호까지 반복 (j: 1 ~ n-1) 
            next[j] = sum(prev[:j+1]) # 다음 층의 j+1호 인원 수는 이전 층의 j+1호까지의 인원 수의 합
        prev = copy.deepcopy(next) # 다음 계산을 위해 prev를 next로 대체 
    return next[-1] # next의 마지막 값 반환

for _ in range(int(input())):
    k = int(input())
    n = int(input())
    print(apt(k, n))

코드가 복잡하다. 내가 봐도 헷갈려서 주석을 달아놨다.
그리고 next를 [1] * n으로 초기화한 것도 마음에 들지 않는다.

deep copy를 쓴 이유에 대해 설명하자면,

# 오류 코드

def apt(k, n): 
    prev = [i for i in range(1, n+1)]
    next = [1] * n

    for _ in range(k):
        for j in range(1, n):
            print(f"k = {k}, j = {j}")
            print(f"prev = {prev}")
            next[j] = sum(prev[:j+1])
            print(f"next = {next}")
        prev = next # 오류 -> 얕은 복사
    return next[-1]


for _ in range(int(input())):
    k = int(input())
    n = int(input())
    print(apt(k, n))

위 코드의 실행 결과는 다음과 같다.

k = 2, j = 2에서, prev = [1, 3, 6]을 의도했는데, 의도와 달리 [1, 4, 6]이 저장돼있다.
이처럼 = 혹은 : 연산자로 얕은 복사를 하다보면 의도치 않은 동작을 하기도 한다.
따라서 deep copy를 사용하였다.

추가

팀원 발표를 들고 알았는데, list를 복사할 때 b_list = list(a_list)로 복사할 수 있다고 한다. deep copy를 쓰는 것보다 간단해서 좋다.

def apt(k, n): 
    prev = [i for i in range(1, n+1)]
    next = [1] * n

    for _ in range(k):
        for j in range(1, n):
            next[j] = sum(prev[:j+1])
        prev = list(next)
    return next[-1]

for _ in range(int(input())):
    k = int(input())
    n = int(input())
    print(apt(k, n))

풀이 2

for _ in range(int(input())):
    k, n = int(input()), int(input())
    prev = list(range(1, n+1))
    next = [1] * n
    
    for _ in range(k):
        for i in range(1, n):
            next[i] = prev[i] + next[i-1]
        prev = next
    print(next[-1])

다른 방식으로 계산해보았다. 풀이 1보단 깔끔한 것 같은데 여전히 next가 마음에 들지 않는다.

풀이 3 (참고)

for _ in range(int(input())):
    k, n = int(input()), int(input())
    now = list(range(1, n+1))
    for _ in range(k):
        for i in range(1, n):
            now[i] += now[i-1]
    print(now[-1])