- C언어 : 기본수학1(6)
11.JUL.2022
문제 : 기본수학1
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터
b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때,
주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라.
단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.문제 풀이
#include <stdio.h>
int main()
{
int test, k, n; // k == 층, n == 호
scanf("%d", &test);
for (int i = 0; i < test; i++) {
scanf("%d %d", &k, &n);
printf("%d\n", apart(k, n)); // apart(a, b) == a층 b호에 사는 사람 수를 구해준다
}
return 0;
}
int apart(int k, int n) { // apart( ) 구현 부분
int sum = 0;
if (k == 0) // 문제 제시 : 0층 부터 시작, 0층의 i호에는 i명이 산다
return n; // ---> 0층일 때 n 명이 산다
else if (n == 1) // 1호에는 층수 관계 없이 1명만 산다
return 1;
else { // 각 층, 각 호에 사는 사람들을 더한 최종 sum을 RTN(재귀 함수 이용)
for (int i = 1; i <= n; i++) {
sum += apart(k - 1, i);
}
return sum;
}
}나는 재귀함수로 풀었는데, 구글링 했을 때는 배열을 이용한 풀이가 많아 보였다.
음 근데 구글링 풀이들은 한눈에 이해하기에는 너무 어려워 보였어...숙취로 눈이 반쯤 감겨서 그른가...🙄🙄 눈에 코드가 안 들어오는 날이구먼
main 부분 자체는 매우 간단하다.
단지 각 층, 각 호에 사는 사람 수를 구하려면 0층~입력한 k 층 n호까지의 사람을 더해서 구해야 하는데, 이럴 때 유용한 게 재귀함수다. 재귀함수로 사람 수를 구하기 위해 apart 함수를 구현해 보았다.
사람 수를 더할 sum을 일단 선언해 주고, 생각을 해보자.
층이 0층부터 시작한다고 되어 있는데 문제에서는 0층 i호에 i명이 산다고 되어 있다. 쫄지 말자 n호에 n명이 산다는 거다. i는 훼이크로 헷갈리게 더 넣은 건가??
아무튼 그래서 층 수인 k == 0이라면 n호에 사는 사람은 n명이다.
또 n호가 1이라면?? 조건을 봤을 때 1호에는 반드시 1명만 살게 된다. 부럽다.
n==1이라면 1명이다.
이제 기타를 생각해 보자.
a-1층에는 1호부터 b호까지 사람들의 수를 더한만큼 산다고? 끔찍하네.
이 끔찍한 조건을 재귀함수로 쓰자.
예를 들어 k==2, n==3이라고 하면 apart에서 else의 for문에서,
apart(2-1, 1~3까지) --> 즉 1층에서 1호 + 2호+ 3호 사람 수를 더하라는 건데
이 1층 사람들 수는 어떻게 구하냐면 다시 else의 for문에서,
apart(1-1, 1~3까지) --> 이때는 k == 0이므로 1호에 1명~3호에 3명이 산다고 구할 수 있다.
나는 보통 풀이를 거꾸로 푼다고 생각하고 구현한다.
재귀함수는 이름만 어렵고 구현할 줄만 알면 매우 편하다.
