[C언어] 백준 2775 : 부녀회장이 될테야

문제는 간단하다. 맨 왼쪽 층수는 1 고정, 맨 아랫층 인원수는 1씩증가한다.

보고 이차원배열을 떠올렸고, arr[i][j] = arr[i-1][j] + arr[i][j-1]식을 생각해냈다.

하지만, 제한조건에 따라 k(층수)값만큼 반복문을 돌려 답을 출력하려고 했지만, 앞에 t값을 받아 t횟수만큼의 k와 n(동)을 입력을 해야하기때문에 논리는 맞지만 정답이 도저히 안나왔다.

결국 구글링을 했고, 거의 모든 사람들이 arr[15][15]로 지정해서 풀었는데, n의 범위가 제한조건에서 n <= 14 이기에 납득이 되었지만, k는 1 <= k로 조건이 지정되어있기에 15로 하는 이유를 이해하지 못했다.

코드를 다 뜯어고쳤음에도 안나왔고, 구글링을 해도 다 arr[15][15]로 진행했다.

이유를 찾아보니 과거 조건에는 k 또한 1 <= k <= 14라고 되어있었다. 하지만 문제가 업데이트 되었다.

결국 나도 포기하고 arr[15][15]의 아이디어만 갖고 문제를 풀었다.

내가 푼 풀이

#include <stdio.h>

int main()
{
    int i,j;
    int t,k,n;
    int arr[15][15] = {0, };
    
    i = 0;
    while(i < 15)
    {
        arr[0][i] = i; // 맨 아래 사람들은 다 i명이다.
        i++;
    }
    i = 1;
    while (i < 15)
    {
        arr[i - 1][1] = 1; // 맨 왼쪽 층수는 전부 1이다.
        j = 1;
        while(j < 15)
        {
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            j++;
        }
        i++;
    }
    scanf("%d", &t);
    i = 0;
    while(i < t)
    {
        scanf("%d %d", &k, &n);
        printf("%d\n", arr[k][n]);
        i++;
    }
}

다른 사람 풀이

#include <stdio.h>
int main(void)
{
    int t, k, n, i, j, l;
    int arr[15][15] = {0, };
    for (i = 0; i < 15; i++)
        arr[0][i] = i;
    for (i = 1; i < 15; i++)
        for (j = 1; j < 15; j++)
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
    scanf("%d", &t);
    for (i = 0; i < t; i++)
    {
        scanf("%d %d", &k, &n);
        printf("%d\n", arr[k][n]);
    }
    return 0;
}

출처: https://travelerfootprint.tistory.com/41 [나그네의 발자취]