[C]백준_2775 : 부녀회장이 될테야

2022년 7월 3일에 작성됨

 

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

2775번: 부녀회장이 될테야

 

 

문제 분석

어떠한 아파트에 "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 합만큼 사람들을 데려와야 살아야 하는 규칙"의 아파트가 있다. 예를 들어 5층 2호에 살려면 4층 1호~2호의 사람들의 합만큼 살아야 한다.

 

<조건>

• 빈 집이 없다.
• 아파트는 0층부터 있으며 각층에는 1호부터 있다.
• 0층의 i호에는 i명이 산다.
• 아파트의 층과 호수는 14와 같거나 작다. (아파트의 층과 호수에 관한 배열을 각각 15로 만들어준다)

 

예를 들어 2층 3호의 사람 수를 구한다고 해보자. 문제에서 주어진 규칙에 따르면, 1층의 1호~3호까지 사람들의 합을 구하면 된다.

그런데 1층 1호~2호의 사람 수는 2층 2호의 사람 수와 같으므로 결론적으론 2층 2호 + 1층 3호 = 4 + 6 = 10명이 된다.

이를 배열을 이용하여 나타내면 arr[2][3] = arr[2][2] + arr[1][3] = 4 + 6 = 10으로 나타낼 수 있다. 즉, arr[i][j] = arr[i][j-1] + arr[i-1][j]이 된다.

 

 

소스 코드 (⭕)

#include <stdio.h>
int main()
{
    int arr[15][15] = { 0, };		// 각각 크기 15인 2차원 배열을 선언하고 0으로 초기화
    int test, k, n, i, j;

    for (i = 0; i < 15; i++) {
        arr[0][i] = i;			// 0층의 i호에는 i명 만큼 산다고 했으므로 0층에는 i명으로 선언
    }
    for (i = 1; i < 15; i++) {
        for (j = 1; j < 15; j++) {
            arr[i][j] = arr[i][j - 1] + arr[i - 1][j];		// 사람들의 합을 arr[i][j]에 넣어준다
    }
        }
    scanf("%d", &test);			// test case의 수 입력

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

 

코드 분석

1. 층수(k)는 0~14층까지 있고, 호수(n)는 1~14호 까지 있다. 따라서 배열을 각각 크기가 15인 2차원 배열을 선언하고 0으로 모두 초기화 해준다.

 

2. 문제에서 0층의 i호에는 i명 만큼 산다고 하였으므로 0층의 i호는 i명으로 선언해주는 반복문을 사용한다.

 

3. 조건에서 빈 집이 없다고 하였으므로 for 문을 이용하여 모든 층과 호의 arr[i][j] 값을 구해준다.

 

4. 그 다음 test case를 입력하여 몇 번 반복 할 것인지 정하고, 층수(k)과 호수(n)를 입력하면 그 위치의 값인 사람들의 합이 출력된다.

 

 

 

end

처음엔 문제가 이해가 안돼서 어떻게 풀어야 할 지 막막했는데 다른 분들의 설명과 코드를 참고해서 다시 보니까 문제와 코드 돌아가는 원리가 이해되기 시작했다. 배열이 엄청 어렵게 느껴졌었는데 서서히 할 만 하다고 느껴지는 것 같아 뿌듯하기도 하고..ㅎㅎ