[백준] C 21일차 (부녀회장이 될테야 #2775번)

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

2775번: 부녀회장이 될테야

---

1. 문제

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

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

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

 

2. 입력

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

 

3. 출력

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

 

 

4. 문제풀이

출처: https://crazykim2.tistory.com/586

arr[i][j]  =  arr[i][j-1]   +   arr[i-1][j];

 

 

1) 런타임 에러

#include <stdio.h>
#include <stdlib.h>

void find(int k, int n){
    int arr[k][n];
    
    for(int i=0; i<n; i++){
        arr[0][i]=i+1;
        //printf("arr[0][%d]= %d\n",i,arr[0][i]);
    }
    
    for(int i=1; i<=k; i++){
        for(int j=0; j<n; j++){
            if(j==0){
                arr[i][j]=1;
                //printf("arr[%d][%d]=%d\n",i,j,arr[i][j]);
            }
            else{
                arr[i][j]=arr[i][j-1] + arr[i-1][j];
                //printf("arr[%d][%d]=%d\n",i,j,arr[i][j]);
            }
    }
    printf("%d\n", arr[k][n-1]);
    }
}

int main()
{
    int test,k,n;
    scanf("%d",&test);
    
    for(int i=0; i<test; i++){
        scanf("%d",&k);
        scanf("%d",&n);
        find(k,n);
    }

    return 0;
}

접근 방식

15,15,배열로 깔 필요 없이 scanf로 받을 때, 1층 3호면 1층 3호까지만 배열로 만들면 되겠지? 

근데 한번만 받는 것이 아니라 여러번 scanf로 받아서 k,n이 변경되면 그때마다 아파트 주민수 배열을 처음부터 다시 해야 함 -> 시간 오래 걸림, arr 중복

 

 

2) 15,15 배열을 미리 깔아 놓자 (최종)

#include <stdio.h>
#include <stdlib.h>

int arr[15][15];
    
void find(){
    for(int i=0; i<15; i++){
        arr[0][i]=i+1;
    }
    
    for(int i=1; i<=15; i++){
        for(int j=0; j<15; j++){
            if(j==0){
                arr[i][j]=1;
            }
            else{
                arr[i][j]=arr[i][j-1] + arr[i-1][j];
            }
        }
    }
}

int main()
{
    int test,k,n;
    scanf("%d",&test);
    find();
    
    for(int i=0; i<test; i++){
        scanf("%d",&k);
        scanf("%d",&n);
        printf("%d\n",arr[k][n-1]);
    }

    return 0;
}

---

6. 결과