14225
-
BOJ 14225 : 부분수열의 합백준 문제풀이/BRUTE FORCE 2020. 6. 5. 00:30
문제 문제 풀어보기 풀이 완전 탐색을 하는데 중복되는 계산을 줄여주는 방법을 선택합시다. 재귀 문을 보면 그냥 포문 돌면서 하나씩 다 더해보는 겁니다. 그런데 저기서 st 인자를 없애고 모두 처음부터 본다면 어마어마한 중복이 발생합니다. 예를 들어 1, 2, 3, 4의 인자가 있다면 st 인자없이 모두 처음부터 탐색을 하는 경우 이러한 순서로 탐색할 겁니다. 하지만 현재 선택한 인덱스보다 작은 인덱스를 선택하는 경우는 모두 중복 수열이 됩니다. 따라서 st 인자를 사용해서 이전 인덱스는 넘어가게 해 줍시다. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) x>=8 || x