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

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

2775번: 부녀회장이 될테야

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int t, k, n;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d%d", &k, &n);
        
        int** arr = (int**)malloc(sizeof(int*) * (k+1));
        for (int j = 0; j <= k; j++) {                  //호수는 1호부터이나 층은 0층부터이기 때문
            arr[j] = (int*)malloc(sizeof(int) * n);     //2차원 배열 동적할당
        }

        for (int x = 0; x <= k; x++) {                  //마찬가지로 0층부터이기 때문
            for (int y = 0; y < n; y++) {
                if (x == 0) { arr[x][y] = (y + 1); }
                else if (y == 0) { arr[x][y] = 1;  }
                else { arr[x][y] = arr[x - 1][y] + arr[x][y - 1]; }
            }
        }

        printf("%d\n", arr[k][n - 1]);                  //마찬가지
        for (int i = 0; i < k; i++) {                   //2차원배열을 동적할당한 메모리 공간 해제
            free(arr[i]);
        }
        free(arr);
    }
    return 0;
}

아파트 구조를 보면 항상 2차원 배열이 먼저 떠오른다.

사실 동적할당을 굳이 하지 않더라도 1 ≤ k, n ≤ 14라는 조건이 있었기 때문에

arr[15][15]로 2차원 배열을 선언해주어도 되었지만 그냥 동적할당 하고 싶었다. 복습할겸.

동적할당 하지 않았으려면 반복문이 3개로 줄었겠죠?

 

코드를 설명하기 위해 예를 들어보자.3층에 4호에는 몇 명이 사는지 알고 싶다.

첫 번째

각 층의 1호와 0층의 모든 호수들은 따로 구분했다.

모든 1호에는 1명씩 들어갈 것이고

0층에는 첫째항이 1이고 공차가 1인 등차수열이 호수에 따라 존재한다.

17,18번 코드에 나타난다.

 

두 번째

 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

그렇다면 1층 3호의 사람의 수는 0층 1호의 사람의 수 + 0층 2호의 사람의 수 + 0층 3호의 사람의 수여야 하지만0층 1호의 사람의 수 + 0층 2호의 사람의 수는 1층 2호의 사람의 수이기 때문에1층 3호의 사람의 수는 1층 2호의 사람의 수 + 0층 3호의 사람의 수가 된다.19번 코드에 나타난다.

 

위 두 규칙은 1 ≤ k, n ≤ 14의 k,n이 무엇이든 성립한다.가장 핵심은 두 번째 규칙을 찾는 것이었다.재귀도 생각나고 피보나치도 생각났는데 내 머리가 부족한 것인지 구현하지 못했다.0층부터 시작한다는 것에 주의하며 코드를 짜자.

 

다른 사람의 코드

#include <stdio.h>

int Recursive(int Floor, int RoomNum);

int main()
{
        int Case;
        int Floor, RoomNum;       // 1 <= Floor, RoomNum <= 14

        // 가장 간단한 방법은 반복문으로 값 중첩
        // 예외처리 필요
        // 코드를 간단하게 하려면 재귀 함수를 사용할 수 있음
        scanf("%d", &Case);
        for(int i=0; i<Case; i++){
                scanf("%d %d", &Floor, &RoomNum);
                printf("%d\n", Recursive(Floor, RoomNum));
        }
}

int Recursive(int Floor, int RoomNum){
        int Person=0; // 호출마다 값 저장
        // printf("Floor= %d, RoomNum= %d\n", Floor, RoomNum);
        
        // 0층 일때 값 반환, 방 번호 == 사람 수
        if(Floor==0) return RoomNum;
        // 1호실은 항상 1명으로 고정
        else if(RoomNum==1) return 1;
        else{
                // 끝점(0층)부터 값 중첩
                for(int i=RoomNum; i>0; i--){
                        Person += Recursive(Floor-1, i);
                        // Recursive(4-1, 8) = 0
                        // Recursive(3-1, 8) = 0
                        // Recursive(2-1, 8) = 0 ....
                        // Floor가 0에 도달하면 RoomNum(i)이 차감되며 값을 반환
                }
        }
        return Person;
}
https://small-pond.tistory.com/108

재귀가 되는 거였다니. 재귀에 대해 깊게 공부해보지는 못하고 그냥 체크만 하고 넘어갔었었다.

"재귀 함수를 적용할 수 있는 문제는 특징이 있는데 구하려는 값 안에 작은 값들이 동일하게 중첩되어 있는 형태다."

출처에 나온 코드의 게시자 분께서 하신 말씀이다. 다시 한번 되새기고 간다. 위 문장이 곧 재귀라는 것을