C언어 2775번 부녀회장이 될테야 풀이

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

2775번: 부녀회장이 될테야

문제

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

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

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

 

풀이

 

문제에 대한 이해 

 

문제를 풀이하면, 다음과 같이 입력된다.

1	7	28	84	210	462
1	6	21	56	126	252
1	5	15	35	70	126
1	4	10	20	35	56
1	3	6	10	15	21
1	2	3	4	5	6

 

idea

1)arr[i][j] = arr[i-1][j] + arr[i][j-1] 

 

2)1 ≤ k, n ≤ 14 이므로 배열은 14 x 14 의 형태

0~14이므로 15 x 15의 형태

 

3)맨 왼쪽줄은 1 , 맨 아래줄은 순서대로 1 2 3 4 5 이므로 일단 기초가 되는 부분들을 채우고 배열 채우기.

 

 

직관대로 푼 풀이

#include <stdio.h>
int main() {

	int a = 0;
	int b = 0;
	int T = 0; //test case 
	int numArr[15][15] = { 0, };

	//기초배열채우기
	for (int j = 0; j < 15; j++) //맨 아랫줄
	{
		numArr[14][j] = j + 1;
	}
	for (int i = 0; i < 15; i++) //맨 왼쪽줄
	{
		numArr[i][0] = 1;
	}

	for (int i = 14; i > 0; i--)
	{
		for (int j = 1; j < 15; j++)
		{
			numArr[i - 1][j] = numArr[i][j] + numArr[i - 1][j - 1];
		}
	}


	for (int i = 0; i < 15; i++) //배열 체크하기
	{
		for (int j = 0; j < 15; j++)
		{
			printf("%8d ", numArr[i][j]);
		}
		printf("\n");
	}

	//
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		scanf("%d", &a);
		scanf("%d", &b);
		printf("%d\n", numArr[14 - a][b - 1]);
	}

	return 0;
}

 

실행결과

위의 코드들을 보면 알겠지만, 이렇게 풀면 우리의 직관과 컴퓨터의 배열에 실제로 입력되는 것이 달라 이해하기도 어렵고 코드를 짜기도 어렵다.

(우리 직관으로 0층은 아래에 있어야하나, 배열에서 0층은 맨 위)

따라서, 아예 0층이 맨 위에 있는 것으로 생각하고 푸는 것이 좀 더 효과적이다.

 

 

직관X 정답풀이

#include <stdio.h>
int main() {

	int a = 0;
	int b = 0;
	int T = 0; //test case 
	int numArr[15][15] = { 0, };

	//기초배열채우기
	for (int j = 0; j < 15; j++) //맨 아랫줄
	{
		numArr[0][j] = j + 1;
	}
	for (int i = 0; i < 15; i++) //맨 왼쪽줄
	{
		numArr[i][0] = 1;
	}
	
	for (int i = 1; i < 15; i++)
	{
		for (int j = 1; j < 15; j++)
		{
			numArr[i][j] = numArr[i - 1][j] + numArr[i][j - 1];
		}
	}
	

	for (int i = 0; i < 15; i++) //배열 체크하기
	{
		for (int j = 0; j < 15; j++)
		{
			printf("%8d ", numArr[i][j]);
		}
		printf("\n");
	}
	
	
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		scanf("%d", &a);
		scanf("%d", &b);
		printf("%d\n", numArr[a][b-1]);
	}
	
	return 0;
}

Q)배열 크기 15인 이유는 무엇인가?

0층부터 ~14층이므로 총 15개의 층으로 구성되어있는 것

 

 

Q)왜 numArr[a][b]가 아니라 numArr[a][b-1]일까?

실제로 배열은 이렇게 되어있고,예를들어 1층의 3호일때 빨간색 6을 출력해야한다. 하지만실제로 numArr[1][3]은 파란색 10이므로 index를 한칸 줄이기 위해 b-1을 한 것

 

이해를 돕기 위해 배열을 시각화 했다. 

 

배운 점

• 15x 15정도는 계산하는데 얼마 안걸리므로 다 채우고 시작해도 된다.
• 반대로 생각해도 된다.. 배열의 특성상.