[백준/C++]#9095 - 1, 2, 3 더하기

풀이

#include <iostream>
using namespace std;
 
int main() {
	int t;
	cin >> t;		// 테스트의 개수를 받음
	while (t--) {	// 그만큼 반복
		int n;
		cin >> n;
		int D[1001];
		D[1]=1, D[2]=2, D[3]=4;
			for (int i=4; i<=n; i++) {		// n의 크기에 따라 반복
				D[i] = D[i-1] + D[i-2] + D[i-3];	// 값을 배열에 저장
		}
		cout << D[n] << '\n';
	}
	return 0;
}

개념

2xn 타일링과 다르게 생겼지만 유사한 문제이다.

2xn 타일링 = 정수 n을 1, 2로 나타내는 법이다.

문제는 Bottom-Up 방식으로 해결했다.

---

풀이 

정수 n을 1, 2, 3으로 나누어 나타내는 경우의 수는 D[n]이다.

①D[n-1]에 1더하기

②D[n-2]에 2더하기

③D[n-3]에 3더하기

D[n]은 위 3개의 합이다.

 

따라서 D[n]은 D[n-1] +D[n-2] + D[n-3]이다.

 

---

+a

저번 문제들과 조금 다른 점은 테스트받을 개수를 받아서, 그만큼 시행했다는 것이다.

이중 반복문이므로, 시간초과가 날법한데도 잘 컴파일 되었다.

여기엔 배열에 저장하는 이점이 따로 구현되지 않았으므로, 이번엔 Bottom-up 방식을 사용했다.

초기에 n에 높은 값이 입력되는 경우를 생각했을 때, 이 방식도 메리트가 있어보인다.

#include <iostream>
using namespace std;
 
int D[1001];
int devide(int k){
	if (k == 1) return 1;
	if (k == 2) return 2;
	if (k == 3) return 4;
	if (D[k] > 0) return D[k];	// D[k]에 앞서 값이 대입된 경우 출력
	D[k] = devide(k-1) + devide(k-2) + devide(k-3);
	return D[k];
}
 
int main() {
	int t;
	cin >> t;
	while (t--) {		// 테스트 횟수만큼 반복
		int n;
		cin >> n;
		cout << devide(n) << '\n';
	}
	return 0;
}