[Baekjoon] [2775 : 부녀회장이 될테야]

저는 원래 간단한 문제도 복잡하게 푸는걸 잘 합니다.

굉장히 한심한 편이죠.

 

그래서 그런지.. 문제를 풀 때마다 간단한 문제도 이런 식으로 풀곤 합니다.

 

baekjoon 기본 수학 1 문제집에 있는 문제여서 수학적인 개념으로 풀어보고자 했습니다.

 

메모장에 숫자를 적어나갔습니다.

 

 

 

층 별 계수

1 5 15 35
1 4 10 20
1 3 6 10 
1 2 3 4 
1 1 1 1 

 

층 : 호수에 따른 숫자
4 : 1 (1*4 + 2*1) (1*10 + 2*4 + 3*1) (1*20 + 2*10 + 3*4 + 4*1)
3 : 1 (1*3 + 2*1) (1*6 + 2*3 + 3*1) (1*10 + 2*6 + 3*3 + 4*1)
2 : 1 (1*2 + 2*1) (1*3 + 2*2 + 3*1) (1*4 + 2*3 + 3*2 + 4*1) 
1 : 1 (1*1 + 2*1) (1*1 + 2*1 + 3*1) (1*1 + 2*1 + 3*1 + 4*1) (1+2+3+4+5)
0 : 1 2 3 4 5

 

계속 보다보니 계수에 대한 규칙이 보였습니다.

 

가장 아래 층을 1 1 1 1로 두면 계산을 한 번 더 하지만 코딩할 때 층 수 계산이 편할 거 같아서.. 그랬습니다.

 

떼어놓고 봅시다

 

1 3 6 10

1 2 3 4

1 1 1 1

 

모든 층의 1호는 1이라는 것을 알 수 있습니다.

 

2층에서 1 3 6 10 중 3을 만들기 위해서 왼쪽 숫자 1과 아래 숫자 2를 더해서 만든다는 것을 알 수 있습니다.

 

 

ㅁ -> +

        ^

         |

        ㅁ

 

왼쪽, 아래 두 숫자를 더한 값이 되는거죠.

 

그 점에 주목해서 코드에는

for(j=1; j<k; j++)
{
	c[1] += 1;

	for(m=2; m<14; m++)
	{
	c[m] += c[m-1];
	}	
}
for(j=1; j<=n; j++)
{
	tot += c[n-j]*j;
}

이런 부분이 있습니다.

어차피 1번 요소에는 0번 요소인 1이 더해질테니 +=1을 하고

2번부터는 이전 요소와 현재 자신을 더해서 새로운 배열을 만들어가기 때문에 c[m] += c[m-1]을 했습니다

합에 대한 결과는 위에서 층에 따른 숫자를 보면 1, 2, 3, 4 늘면서 계수는 앞서 계산한 배열의 역순으로 가므로

tot += c[n-j] * j를 했습니다.

 

그래서 답은 다음과 같았습니다.

 

#include<stdio.h>

int main()
{
	int i,j,m;
	int t;
	int k,n;
	int c[14];
	int tot=0;
	
	for(i=0; i<14; i++)
	{
		c[i] = 1;
	}
	
	
	scanf("%d",&t);
	
	int ans[t];
	
	for(i=0; i<t;i++)
	{
		scanf("%d %d",&k,&n);
		if(k==0)
		{
			ans[i] = n;
			continue;
		}
		else
		{
			for(j=1; j<k; j++)
			{
				c[1] += 1;
				
				for(m=2; m<14; m++)
				{
					c[m] += c[m-1];
				}
			}
			for(j=1; j<=n; j++)
			{
				tot += c[n-j]*j;
			}
			ans[i] = tot;
			tot = 0;
			for(j=0; j<14; j++)
			{
				c[j] = 1;
			}
		}
	}
	
	for(i=0; i<t; i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

처음에는 다음 층, 호수를 받을 때 배열을 다시 초기화하지 않아서 틀렸네요..

여러번 테스트케이스를 받을 때 초기화하는 것을 신경써야겠습니다.