문제접근
•
숫자의 종류는 정해져 있다
•
그 숫자들을 차례로 더해서 set에 넣게 되면 set에서 중복이 제거 되기 때문에 원하는 답을 구할 수 있음
•
set의 경우 정렬을 하기 때문에 이 경우 굳이 필요없어서 unordered_set을 하면됨
놓쳤던 부분
•
불필요한 계산까지 같은 계산을 계속 반복하여 시간초과
→ 재귀를 타고 들어갈때 index까지 같이 넘겨주어 불필요한 계산을 피한다
코드
2152 KB
0 ms
#include <iostream>
#include <unordered_set>
int n;
int number[4] = {1, 5, 10, 50};
std::unordered_set<int> answer;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n;
}
void solution(int num, int count,int index)
{
int tmp;
if (count == n)
{
answer.insert(num);
return ;
}
for (int i = index; i < 4; i++)
{
tmp = num + number[i];
solution(tmp, count + 1, i);
}
}
void print()
{
std::cout << answer.size();
}
int main(void)
{
input_setting();
input();
solution(0, 0, 0);
print();
return (0);
}
C++
복사
