백준 문제 중 2775번, 수학, ‘부녀회장이 될테야’

백준 문제중 2775번

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

문제

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

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

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

입력

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

출력

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

---

풀이

모두가 계약조건에 따른다면 2차원 배열을 선언한뒤 한 층이 올라 갈때마다 각층의 아래층의 n호까지 사람의 합으로 구할 수 있고 이를 코드로 구현 했다.

Issue1

입력으로 받을 k,n 도 2차원 배열을 선언해 데이터를 다루려고 했는데 파이썬으로 2차원 배열 구현이 처음이라 약간의 문제가 생겼다.

# 테스트 케이스수 입렫
case= int(input())

# 2 by case 배열 선언
kn=[[None,None]]*case

print(kn)

# kn[0][1] 인덱스로 접근해서 원소값 변경
kn[0][1]=1

# 의도치 않은 결과 발생
print(kn)

2
[[None, None], [None, None]]
[[None, 1], [None, 1]]

이 문제는 * 연산자의 특징 때문에 발생했다. *연산자는 배열이 값을 각각 할당하는게 아닌 call by reference 즉 참조값을 할당하는 shallow copy 이기 때문이다. 참조값의 메모리에 있는 정보를 바꾸자 같은 참조값을 갖고 있던 인덱스도 변하게 되었다.

이를 해결 하기 위해서는 배열의 원소에 값을 직접 할당하는 접근이 필요하다.

case = int(input())

kn = [[None for _ in range(2)]for _ in range(case)]

print(kn)

kn[0][1]=1

print(kn)

2
[[None, None], [None, None]]
[[None, 1], [None, None]]

리스트 컴프리헨션으로 문제를 해결했다.

# 계약조건에 맞는 인원을 구하는 함수 선언
def contract(k,n):
    # 0~k층 1~n호에 맞기 k+1 by n-1 크기 배열 선언
    a = [[0 for i in range(n)] for j in range(k+1)]     
    
    # 0층 인원 할당
    a[0]=[i for i in range(1,n+1)]

    # k층 n호에는 k-1층 n호까지의 합과 같다
    for i in range(1,k+1):
        
        for j in range(n):
            
            a[i][j] = sum(a[i-1][:j+1])
    
    # 0층에서 k층 순으로 출력
    for x in a[::-1]:
        print(x)

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


# 케이스 수 입력
case = int(input())

# 입력을 저장할 배열 선언
kn = [[None,None] for _ in range(case)]

# kn 입력
for i in range(case):

    kn[i][0]=int(input())

    kn[i][1]=int(input())

# 각각 k n으로 분리
for i in range (case):

    k=kn[i][0]

    n=kn[i][1]

    contract(k,n)

1
5
6
[1, 7, 28, 84, 210, 462]
[1, 6, 21, 56, 126, 252]
[1, 5, 15, 35, 70, 126]
[1, 4, 10, 20, 35, 56]
[1, 3, 6, 10, 15, 21]
[1, 2, 3, 4, 5, 6]
462

배운점

1. 파이썬에서 2차원 배열을 선언하고 다루는 법을 알게되었다.
2. *연산자가 shallow copy 라는걸 알게됐다.