저는 원래 간단한 문제도 복잡하게 푸는걸 잘 합니다.
굉장히 한심한 편이죠.
그래서 그런지.. 문제를 풀 때마다 간단한 문제도 이런 식으로 풀곤 합니다.
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;
}처음에는 다음 층, 호수를 받을 때 배열을 다시 초기화하지 않아서 틀렸네요..
여러번 테스트케이스를 받을 때 초기화하는 것을 신경써야겠습니다.
