[백준] 2775번: 부녀회장이 될테야 풀이 및 해설(C++)

 

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

2775번: 부녀회장이 될테야

풀이

 

동적프로그래밍 문제로, 한 칸 한 칸에 들어가는 모든 값을 계산하면 너무 오랜 시간이 걸린다. 그래서 기존에 계산해 놓은 값을 바탕으로 더 빠르게 값을 찾아야 한다.

 

우선 각 층의 0층에는 호수만큼 산다고 했으니, 다음과 같다.

	1호	2호	3호	4호
3층
2층
1층
0층	1	2	3	4

 

그리고 조건에 맞게 들어가야 되는 인원을 채우면

	1호	2호	3호	4호
3층	1	5	15	35
2층	1	4	10	20
1층	1	3	6	10
0층	1	2	3	4

이렇게 하다보면 한 가지 규칙을 발견할 수 있다.

 

a층 b호에 사는 사람의 수를 X(a, b)라고 표현하자.

 

그러면 X(a,b)= X(a-1, b)+X(a, b-1)이다.

 

그 이유는 무엇일까?

규칙에 따르면

X(a, b)= X(a-1,1)+X(a-1,2)...+X(a-1, b-1)+X(a-1, b)이고,

X(a-1, b)= X(a-2,1)+X(a-2,2)...+X(a-2, b-1)+X(a-2, b),

X(a, b-1)= X(a-1,1)+X(a-1,2)...+X(a-1, b-1)이다. 

 

고로, 

X(a, b)

= X(a-1,1)+X(a-1,2)...+X(a-1, b-1)+X(a-1, b)

= X(a, b-1)+X(a-1, b)인 것이다.

 

즉, 이전 밑집과 아랫집을 더하여 구하면 된다.

 

이제 규칙을 알았으니 코드로 구현해 보자.

 

밑집과 아랫집을 더해서 요청한 호수의 사람수를 출력해야 한다.

 

그러기 위해서는 더 층이 낮고, 더 호수가 작은 집부터 차근차근 값을 채워나가면 된다.

 

 

 

해답 코드

#include<stdio.h>
#include<math.h>


int main(void){
	int apart[15][15]; //층과 호수를 표현하는 2차원 배열을 선언 
	for (int i=0; i<15; i++){
	apart[0][i]=i;	//0층 i호 모두 채우기
	}
	for (int n=0; n<15; n++){
	apart[n][0]=0;	// n층 0호 모두 0명으로 채우기(원래 문제에서는 0호가 없으니 0명이나 마찬가지다.)
	}
	for(int j=1;j<15;j++){
		for(int k=1;k<15;k++){
					apart[j][k]=apart[j-1][k]+apart[j][k-1];
			//조건에 맞는 값들을 이전층+ 이전호수로 왼쪽 아래서부터 차근차근 채운다.
				}
	}
	int x=1,y=1,z=1;
	scanf("%d",&x);
	for(int m=0;m<x;m++){
		scanf("%d",&y);
		scanf("%d",&z);
		printf("%d\n",apart[y][z]);
        //입력을 받고 답을 출력한다.

	}
}

 

유의점

문제를 잘못 이해해서 바로 아래층뿐만 아니라 1층부터 바로 아래층까지 다 더해야 하는 줄 알고 헤매었었다... 문제를 제대로 읽도록 하자.