[PS] BOJ_9095

BOJ_9095

💡 생각하자

Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기

먼저, [1 = 1], [2 = 1+1, 2], [3 = 1+1+1, 1+2, 2+1, 3]인 것은 쉽게 구할 수 있다.

주어진 예시 4에 대해서 생각해보자.

4는 1+'3', 2+'2', 3+'1'로 나눌 수 있다.
1) 1+'3'
위에 있는 3에 대한 정보를 활용하면 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3)을 얻을 수 있다.

2) 2+'2'
위에 있는 2에 대한 정보를 활용하면 2+(1+1), 2+(2)를 얻을 수 있다.

3) 3+'1'
위에 있는 1에 대한 정보를 활용하면 3+(1)을 얻을 수 있다.

결과적으로 4를 1, 2, 3의 합으로 나타낼 수 있는 모든 경우의 수를 구할 수 있다.

재귀 관계식
D[n] : n을 1, 2, 3의 합으로 나타내는 방법의 수
D[n] = D[i-1] + D[i-2] + D[i-3] (n >= 3)
D[0] = 1, D[1] = 1, D[2] = 2

- D[0] = 1인 이유?
예를 들어, D[3] = D[2] + D[1] + D[0]이다.

여기서 D[0]가 의미하는 것은 3 + '0'인 경우를 의미한다.
그러므로 D[0]도 1가지 방법으로 간주해야 한다.

💻 구현하자

• 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 함수

int makeSumOf123(int num) {
	for (int i = 3;i <= num;i++) {
		D[i] = D[i - 1] + D[i - 2] + D[i - 3];
	}

	return D[num];
}

• 초기 호출문

// init
D[0] = 1; D[1] = 1; D[2] = 2;
	
for (int i = 0;i < n;i++) {
	scanf("%d", &temp);
	printf("%d\n", makeSumOf123(temp));
}

💥 발전하자

• 개선점

1. 점화식 찾는 감을 키우자.

📌 참고하자

나의 코드(Github)