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

---

문제 이해 단계

 

정수 n이 주어지면, 그냥 1,2,3 합의 조합으로 경우의 수를 구한다.
순서가 바뀌는 것도 다른 경우의 수로 취급한다.

 

---

문제 접근 단계

N이 1일 때부터 하나씩 살펴보겠다.

N = 1 -> 1개
- 1 

N = 2 ->2개
- 1 + 1
- 2

N = 3 -> 4개
- 1 + 1 + 1
- 1 + 2
- 2 + 1
- 3

N = 4 -> 7개
- 1 + 1 + 1 + 1
- 1 + 1 + 2
- 1 + 2 + 1
- 2 + 1 + 1
- 2 + 2
- 1 + 3
- 3 + 1

N = 5 -> 13개
- 1 + 1 + 1 + 1 + 1
- 1 + 1 + 1 + 2
- 1 + 1 + 2 + 1
- 1 + 2 + 1 + 1
- 2 + 1 + 1 + 1
 - 1 + 2 + 2
- 2 + 1 + 2
- 2 + 2 + 1
- 1 + 1 + 3
- 1 + 3 + 1
- 3 + 1 + 1
- 2 + 3
- 3 + 2

이렇게 나열해 봤을 때, 자세히 보면 N이 4,5일 때 패턴을 볼 수 있다.

문제에서 N이 1,2,3의 합으로 이뤄진다고 했는데,
1,2,3일 때의 경우의 수 양상이
4,5에서도 포함돼서 나타나는 것을 볼 수 있다.

N = 4 일 때 맨 처음이 1로 시작하는 합의 조합만 뽑아보면
- 1 + 1 + 1 + 1
- 1 + 1 + 2
- 1 + 2 + 1
- 1 + 3

인데 여기서 맨 앞에 1을 제외하면
뒤에 있는 수는 정확히 N= 3일 때의 합의 조합과 같다.

N = 3 일 때의 합의 경우의 수를 DP(3)이라고 하면
이는 1 + DP(3)이라고 할 수 있다.

이를 이용해서 다른 수들도 나타낼 수 있다.

4 = 1 + 3 = 2 + 2 = 3 +1 이기 때문에
1 + DP(3) = 2 + DP(2) = 3 + DP(1)이다.

우리가 구해야 하는 것은 경우의 수이다.

시작하는 수가 1,2,3으로 모두 다르므로 모두 다른 경우의 수로 볼 수 있다.
따라서 DP(4) = DP(3) + DP(2) + DP(1)이라고 할 수 있다.

이는 N = 5 일 때도 마찬가지일 것이다.
5 = 4 + 1 = 3 + 2 = 2 + 3이기 때문이다.

즉 이를 점화식으로 표현하면
DP(N) = DP(N-1) + DP(N-2) + DP(N-3)이다.

이제 이를 이용해서 코드를 구현해 보겠다.

 

---

문제 구현 단계

int d[12];
int dp(int x) {
	if (x == 1) return d[x] = 1;
	if (x == 2) return d[x] = 2;
	if (x == 3) return d[x] = 4;

	if (d[x] != 0) return d[x];

	return d[x] = dp(x - 3) + dp(x - 2) + dp(x - 1);
}

핵심이 되는 dp함수이다. 매개변수로 N을 받는다.
x가 1,2,3 일 때는 각각의 경우의 수를 미리 반환한다.

그리고 이미 dp값이 있는 경우에는
설정해 뒀던 값을 반환하여 시간낭비를 줄인다.

그리고 위에서 설명했듯이 점화식을 사용해 준다.

아래는 전체코드를 올리고 설명을 마치겠다.

#include <iostream>

using namespace std;

int d[12];
int dp(int x) {
	if (x == 1) return d[x] = 1;
	if (x == 2) return d[x] = 2;
	if (x == 3) return d[x] = 4;

	if (d[x] != 0) return d[x];

	return d[x] = dp(x - 3) + dp(x - 2) + dp(x - 1);
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int T, n;
	cin >> T;

	while (T--) {
		cin >> n;
		cout << dp(n) << "\n";
		for (int i = 0; i < 12; i++) {
			d[i] = 0;
		}
	}
}

테스트 케이스 T가 여러 번이기 때문에 한번 실행할 때마다
배열 d를 초기화해 주는 작업을 추가하였다.

 

---

시행착오

이 문제는 풀 때는 그리 어렵지 않게 풀고
풀이를 블로그에 올리지 않고 있다가 발표 준비로 작성하였다.

근데 내가 쓴 코드를 다시 보니 왜 이렇게 쓴지도 모르겠고
이 문제를 다시 풀어보니 못 풀겠어서 몹시 당황했다.

역시 컨디션 따라 문제를 못 풀 수도 있겠구나도 싶었고, 꺼진 불도 다시 보자 싶었다.