백준 알고리즘 2775번: 부녀회장이 될테야 C언어

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

2775번: 부녀회장이 될테야

1. 코드

#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;
}

 

2. 문제 해결 방식

이 문제에서 나는 각 호실에 들어가는 사람들의 수를 다 구한 다음에 해당하는 호실의 사람들의 수를 구하는 식으로 구현했다. 일단 먼저 해야 할 것은 배열을 0으로 전부 초기화하고 맨 밑 줄은 i값을 이용하여 채운다. 그다음은 조금 계산을 해본다면 층을 i라고 하고 호를 j라고 가정하고 이것을 배열로 만든다면 arr[ i - 1 ][ j ] + arr[ i ][ j - 1 ] = arr[ i ][ j ]라는 공식이 성립된다.

그렇게 구한 공식을 이용하여 문제에서 원하는 호실의 인원들을 채워 넣는다. 그리고 k, n을 입력받아 해당하는 호실의 인원을 출력하면 된다.

그런데 이때 왜 배열을 15*15 크기로 만든 지 궁금증이 들 수 있다. 그 이유는 문제를 읽어보면 호실은 무조건 1호실부터 14호실까지 있다. 그렇기 때문에 0은 자동으로 제외되기에 14를 초과한 크기가 필요하여 15*15 크기로 만들었다.

3. 느낀 점

처음 이 문제를 봤을 때 이것도 공식이 필요한 문제인가 아니면 그냥 다 채워 넣고 풀어야 하나 고민하기 시작했다. 예전에 나였더라면 그냥 반복문을 해서 채워 넣고 빨리 끝내야겠다는 생각밖에 안 했을 거다. 하지만 이번에는 공식을 이용해서 풀 수 없을까?라는 생각을 했다는 거에 나는 오늘 정말 많은 뿌듯함을 느꼈다.

앞으로 오늘처럼 한 가지 방법만을 생각하는 것이 아니라 여러 가지 생각을 해봐야겠다.