[BaekJoon 9095][⚪3] 1, 2, 3 더하기
❓ 문제
🎯 난이도
Silver ⚪3
🧠 풀이
1. 내 풀이 (DP)
- 알고리즘
Dynamic Programming
- 설명
DP 알고리즘을 사용한 풀이이다.
이 문제는 다음과 같은 DP 알고리즘에 부합하는 조건들이 존재한다.
1, 2, 3만을 조합하여 수를 만드는 경우의 수 문제이다.N에 대한 답을 더 작은 수들의 답으로 표현 가능하다.- 같은 부분이 반복해서 등장하고, 그 결과를
재활용가능하다.
따라서 이러한 조건과 동시에 마지막에 붙는 수가 무조건 '1, 2, 3' 중 하나라는 사실과 결합하면 다음과 같은 점화식이 만들어진다.
\[dp[n] = dp[n-1] + dp[n-2] + dp[n-3]\]
이 점화식을 사용하면 문제가 쉽게 풀린다.
한 번의 반복문으로 모든 DP 배열을 채울 수 있으므로, 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
vector<int> vecNum(iT); // 입력값 저장
int iMax{}; // 입력값의 최대값 저장
for(int& iNum : vecNum)
{
cin >> iNum;
iMax = max(iMax , iNum);
}
vector<int> vecDP(max(3, iMax) + 1); // DP 배열
vecDP[0] = 1; // 아무것도 안하는 경우 1가지
vecDP[1] = 1; // (1)만 들어가는 경우 1가지
vecDP[2] = 2; // (1 + 1), (2) 들어가는 경우 2가지
for(int i = 3; i <= iMax; ++i)
{
// 점화식에 따라 DP 배열 저장
vecDP[i] = vecDP[i - 1] + vecDP[i - 2] + vecDP[i - 3];
}
// 입력값에 따른 DP값 출력
for(int iNum : vecNum)
{
cout << vecDP[iNum] << '\n';
}
return 0;
}
2. 추가 풀이 (BFS)
- 알고리즘
Graph Search,BFS
- 설명
BFS 그래프 탐색 알고리즘을 사용하는 방식이다.
DP 뿐만이 아니라 또 다른 하나의 알고리즘을 사용할 수 있다고 생각해 나온 풀이이다. 기본적으로 입력값이 있으면, 그 입력값에서 1, 2, 3 중에 하나를 골라서 뺄 수 있고, 그 다음도 같은 방식으로 반복 가능하다. 이런식으로 '0'이 될 때까지 세 값 중에 하나를 계속해서 골라가는 것을 반복하고 그 경로를 '카운팅'하면 'BFS'를 통한 풀이가 완성된다.
기본적으로 모든 경우에 대한 경로를 계속해서 저장하는 방식이기에, DP보다 시간도 느리고 메모리도 많이 소비된다.
매 루프마다 1, 2, 3 중 하나의 값을 선택해가는 것을 반복하기에, 시간 복잡도는 O(3ⁿ)라고 볼 수 있다.
- 코드
내 풀이 코드
#include <iostream>
#include <queue>
using namespace std;
int BFS(int iInput);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
while(iT--)
{
int iInput{};
cin >> iInput;
// BFS 결과 출력
cout << BFS(iInput) << '\n';
}
return 0;
}
int BFS(int iInput)
{
int iCnt{}; // 경우의 수를 세어주는 변수
// 목표값에서 빼줄 값들의 후보 배열
int arrNum[3]{ 1, 2, 3 };
queue<int> qBFS{};
qBFS.push(iInput);
while(!qBFS.empty())
{
int iCurr{ qBFS.front() };
qBFS.pop();
// 배열의 후보들을 하나씩 빼는 반복문
for(int i = 0; i < 3; ++i)
{
int iNext{ iCurr - arrNum[i] };
// 0보다 작으면 탈락
if(iNext < 0)
{
continue;
}
// 0이면 카운트 올림
else if(iNext == 0)
{
++iCnt;
}
// 0보다 크면 queue에 push
else
{
qBFS.push(iNext);
}
}
}
return iCnt;
}
💭 후기
기본적으로 이 문제는 DP를 사용하는 것이 정석이지만, 범위가 1 <= n < 11로 매우 좁기 때문에 BFS 같은 그래프 탐색 알고리즘으로도 가능하다. 하지만 기본적으로 '중복'되는 경로가 매우 많고, 분기가 계속해서 갈리는 것이 그대로 'queue'에 저장되기 때문에 시간적으로나, 메모리적으로나 매우 비효율적인 풀이이므로 DP의 점화식을 잘 떠올려 보도록 하자.
Comments