백준 9095 - 1, 2, 3 더하기

C++

9095 번 - 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1
  정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
  문제 출처

접근 방법

입력 되는 수를 [1,2,3]의 합을 구하되, 중복을 허용하므로 [1,2,3]을 각각 더하는 DFS를 호출하며 목표 수에 도달하면 총 횟수를 1 증가한다.
중복을 허용한다는 것은, 1+2+1 과 1+1+2는 다른것으로 생각한다는 것이다.
목표 수보다 더 커지는 것을 탈출 조건으로 DFS를 종료한다.

구현

현재까지 총 합과 목표 수를 DFS의 매개변수로 설정하여, 현재 총 합 수 sum에 1,2,3 각각 더하면서 새로운 DFS를 호출한다.
DFS가 종료 되면, 현재까지 얻은 총 방법의 수를 호출하며 초기화 하여 새로운 목표 수가 설정 된 DFS를 호출한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, result;
void DFS(int, int);
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	int inputN;
	while (n--) {	// n개의 입력을 받는다.
		cin >> inputN;
		DFS(0, inputN);
		cout << result << "\n";		//위 DFS의 결과인 총 방법의 수를 출력하고 0으로 초기화한다.
		result = 0;
	}
	return 0;
}

void DFS(int sum, int targetN) {
	if (sum > targetN)				// 목표 숫자보다 크면 종료
		return;
	else if(sum == targetN){		// 목표 숫자에 도달하면 
		result++;
		return;
	}
	DFS(sum + 1, targetN);
	DFS(sum + 2, targetN);
	DFS(sum + 3, targetN);
}

총평

난이도

⭐★★★★

후기

간단한 DFS라 쉽게 해결 가능하였다.

개선할 점

차후 DP로도 연습해야 할 문제이다.