백준 9095번 : 1,2,3 더하기

문제 접근

---

요즘 구체수학이라는 책을 읽고 있어서 점화식에 꽂혔다. 보니까 점화식으로 풀 수 있을거 같아서 n 에 값을 넣어 경우의 수를 따져봤는데 ans[n] = ans[n-3]+ans[n-2]+ans[n-1] 이라는 게 보였다. ans[n+1] 에 대해서는 가장 마지막 값인 ans[n-3] 을 빼고 ans[n] 을 더하면 되니 ans[n+1] = (ans[n-3]+ans[n-2]+ans[n-1])+ ans[n] - ans[n-3] = 2*ans[n] - ans[n-3] 으로 간략하게 만들었다.

 

n=10 일 때까지 계산에서 ans 배열에 넣어놓은 다음에 n 을 입력받으면 바로 출력되게 구현했다.

 

점화식을 증명해보자.

n=4 인 경우는 아래와 같다.

 

1 1 1 1

1 1 2

1 2 1

2 1 1

2 2

1 3

3 1

 

여기에서 어떻게 규칙을 찾을 수 있을까 고민해보니까, 기존 결과 뒤에 1,2,3 을 붙인것이라고 생각할 수 있었다.

그러니까 n=4 인 경우에 대해 마지막 숫자 기준으로 정렬해보면 아래와 같다.

 

1 1 1 , 1 

1 2 , 1

2 1 , 1

3 , 1

-> n=3 인 경우의 뒤에 1을 붙여 4를 만든 것

1 1 , 2

2 , 2

-> n=2 인 경우의 뒤에 2를 붙여 4를 만든 것

1 , 3

-> n=1 인 경우의 뒤에 3을 붙여 4를 만든 것

 

따라서 ans[n] = ans[n-3] + ans[n-2] + ans[n-1] 이 성립한다는 걸 알 수 있다.

 

 

문제 코드

---

#include <iostream>

using namespace std;

int main(void)
{
	int ans[11], T, n;
	ans[0] = ans[1] = 1;
	ans[2] = 2;
	ans[3] = 4;
	
	for(int i=4; i<11; ++i)
		ans[i] = ans[i-1]*2-ans[i-4];
	
	cin>>T;
	
	for(int i=0; i<T; ++i)
	{
		cin>>n;
		cout<<ans[n]<<'\n';
	}
}