[2775][c] 부녀회장이 될테야. 포인터 수정!!!

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

문제

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

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

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

입력

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

출력

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

 

 

 

맨 처음 문제를 보고 당황스러웠다. room 4개로 3층까지 써보면서

k층 n번 room의 관계식을 만들어보며 규칙을 찾으려 했다.

막막해서 다른 사람들의 풀이를 보았다.

1.직접 [15][15]의 배열을 만들어 일일이 값을 다 계산후 넣어놓고 입력받아 해당 경우를 출력

   -> 일일이 다 계산해야하는 부담이 있다.

2. 관계식을 만들고 초기 일부 값만 넣어놓고 계산하는 방법

 

<풀이>

 위의 2번 방법을 참고해 코드를 만들었다.

 배열의 크기가 15*15인 이유는 층은 0층부터 있기 때문이고 room이 15인 이유는 정확히는 모르겠다. 그냥 필

 아까 위에서 직접 써보았다고 했는데 직접 써보고 나서 보니까

 

 -1번 room의 사람 수는 다 1이 이었고

 -0층의 수는 room 번호와 같았다.

 => 미리 배열에 값을 넣어주어야하는 부분

 

 그리고 찾은 규칙을 통해 함수를 만들어 준다!!!

 관계식을 대체 어떻게 구해야할까

 1번 방법 처럼 미리 다 구해놓지 않는다면 함수를 만들어서 구해야한다는 소린데

 관계식을 어떻게 해야할지 고민이었다.

 Num(k,n) = Num(k-1,n)+Num(k,n-1)

 내가 완전히 다 찾은 관계식은 아니지만...

 그리고 나서 getPeopleNum을 구하는 함수를 따로 만들어준다 => 리커시브하게!!

 

미리 0층과 각 층의 1번 방은 배열에서 0이 아닌 다른 수로 값을 채워넣었음!

이것을 이용해 함수의 내용을 채웠다.

 

 

배열 전역으로 선언

<코드>

int getPeopleNum(int floor, int room);
int people[15][15] = { 0 };

int main(void) {
int caseNum, floor,room,*result;
for (int i = 1; i < 15; i++) {
people[0][i] = i;
people[i][1] = 1;
}
scanf("%d", &caseNum);
result = (int *)malloc((sizeof(int)) * caseNum);
for (int i = 0; i < caseNum; i++) {
scanf("%d", &floor);
scanf("%d", &room);
result[i] = getPeopleNum(floor, room);
}
for (int i = 0; i < caseNum; i++)
printf("%d\n",result[i]);
free(result);
return 0;
}
int getPeopleNum(int floor,int room) {
if (people[floor][room] != 0)
return people[floor][room];
else return getPeopleNum(floor-1, room) + getPeopleNum(floor,room-1);
}

 

 

배열을 전역으로 선언하지 않고 포인터 사용해 인자로 넘긴 경우

<코드2>  어떻게 수정해야할지 모르겠다. 포인터부분 공부 후 다시 수정해보겠다.

#define _CRT_SECURE_NO_WARNINGS
#include
#include
int getPeopleNum(int floor, int room);

int main(void) {
int people[15][15] = { 0 };
int caseNum, floor,room,*result;
for (int i = 1; i < 15; i++) {
people[0][i] = i;
people[i][1] = 1;
}
scanf("%d", &caseNum);
result = (int *)malloc((sizeof(int)) * caseNum);
for (int i = 0; i < caseNum; i++) {
scanf("%d", &floor);
scanf("%d", &room);
result[i] = getPeopleNum(&people,floor, room);
}
for (int i = 0; i < caseNum; i++)
printf("%d\n",result[i]);
free(result);
return 0;
}
int getPeopleNum(int *people[] ,int floor,int room) {
if (people[floor][room] != 0)
return people[floor][room];
else return getPeopleNum(people,floor-1, room) + getPeopleNum(people,floor,room-1);
}