목록1208번 (1)

호지

[백준 알고리즘] 1208번 부분 수열의 합2 문제풀이 c++

반으로 나누지 않으면 시간 초과가 된다. 수열을 반으로 나눠 계산한다. 왼쪽의 경우 가능한 모든 부분 수열의 합을 key로 하여 map에 개수를 저장한다. 오른쪽의 경우 가능한 모든 부분 수열의 합을 s에서 뺀 경우 map에 해당 key가 있다면 결과에 해당 개수를 더한다. 공집합인 경우에도 포함하여 계산되었으므로, s가 0이라면 res를 1감소시킨다. #include #include #include #include #include using namespace std; vector list; int n,s; long long res; map m; void right(int pos, int sum){ if(pos == n){ m[sum] ++; } else{ right(pos+1, sum); right(p..
알고리즘/백준
이전 Prev 1 Next 다음