[BOJ] 2775. 부녀회장이 될테야 (C,Python3)

• 코딩초보. 비효율적인 구현일 수 있음. 

---

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

---

1.Python

 

'''
1 2 3 4 5 6 7
1 3 6 10
1 4 10 20
1 5 15 

'''

t=int(input())
while(t>0):
    k=int(input())
    n=int(input())
    board=[[0]*n for _ in range(k+1)] #2차원 배열 설정
    for i in range(k+1):
        board[i][0]=1

    for i in range(n):
        board[0][i]=i+1
      
    for i in range(1,k+1):
        for j in range(1,n):
            for p in range(j+1):
                board[i][j]+=board[i-1][p]
    print(board[k][n-1])     
    t-=1

각 층마다 값을 차례로 저장해줘야할 것 같아서 2차원 배열로 문제를 접근하고자 했다. 먼저 board에 2차원 배열을 다음과 같이 생성해주었다. (언더바(_)의 의미는 실제 사용하지 않는 변수를 사용할때 사용한다. dummy variable. 그러니까 굳이 for i in range(k+1)로 할 필요가 없는 것이다.) 

 

그리고 주석에 적어놓은것처럼, 각 층의 첫번째(0) 인덱스에는 모두 1이 들어가므로 for 반복문을 사용해 1을 넣어주고, 0층의 경우에는 값이 고정되어 있으므로 1, 2, 3, ...을 차례로 넣어준다. 

 

다음은 각 층마다 값을 계산하여 배열에 저장하도록 삼중 for문을 만들어주었다. 0층의 경우 앞에서 이미 만들어주었으므로 1층부터 검토를 시작한다(i). 그리고 i층 1번 인덱스부터(0번 인덱스에는 이미 1로 저장해둠) 차례로 검토하고(j), 0부터 j번의 인덱스에 저장된 값을 반복해서 i층 j번 인덱스에 저장하도록 한다. (단, i-1층 의 인덱스 값들을 더해야 하므로 [i-1][p]여야 함에 주의.) 

 

이 문제를 풀면서 맞는데 왜 틀리지?를 고민을 많이 했었는데... 인덱스 실수였다. 세번째 for문에서 range(j+1)로, j까지 넣어줘야 하는데 range(j)만 해놓아서 생긴 문제였다. 

---

2.C99

 

#include <stdio.h>

main() {
	int t, k, n;
	scanf("%d", &t);
	while (t>0) {
		scanf("%d\n%d", &k, &n);
		int num[15][15] = { 0, }; 
		for (int i = 0;i<k+1; i++) {
			num[i][0] = 1; 
		}
		for (int i = 0; i < n; i++) {
			num[0][i] = i + 1; 
		}
		
		for (int i = 1; i < k + 1; i++) {
			for (int j = 1; j < n; j++) {
				for (int p = 0; p <= j; p++) {
					num[i][j] += num[i - 1][p]; 
				}
			}
		}
		printf("%d\n", num[k][n - 1]); 
		t--;
	}
}

c언어의 경우 미리 15x15의 2차원 배열에 모두 0을 넣고나서부터 시작했다. (while문을 돌때마다 초기화 시켜줘야하므로 while문 안에 넣었다.)