[BAEKJOON] 1495 기타리스트

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int volSize, startVol, maxVol; scanf("%d %d %d", &volSize, &startVol, &maxVol); vector<vector<int>>DP(1001, vector<int>(1001, -1)); vector<int>vol(101); for (int j = 0; j < volSize; j++) scanf("%d", &vol[j]); DP[0][startVol] = 1; for (int j = 1; j <= volSize; j++) { for (int x = 0; x <= maxVol; x++) { if (DP[j - 1][x] == 1) { if (x + vol[j - 1] >= 0 && x + vol[j - 1] <= maxVol) DP[j][x + vol[j - 1]] = 1; if (x - vol[j - 1] >= 0 && x - vol[j - 1] <= maxVol) DP[j][x - vol[j - 1]] = 1; } } } int answer = -1; for (int j = 0; j <= maxVol; j++) if (DP[volSize][j] == 1) answer = max(answer, j); printf("%d", answer); return 0; }

현재 계산했을 때 큰 값을 저장해서 계산을 했는 데

그건 잘못된 계산이다.

그래서 2진 트리를 만들어 계산하려고 했는데 계산 값이 너무 복잡하고 시간이 너무 오래걸린다

그래서 답을 봤다

요새 너무 안풀린다.

전에는 빠르게 풀었던 것 같은데

암튼

x축은 계산해야하는 볼륨의 개수

y축은 계산해서 나온 볼륨의 값이다

x축의 0에는 시작하는 볼륨의 값에 표시해둔다

그리고 x축에 1을 계산할때

x축 0의 y축 0부터 볼륨의 최대값까지 돈다

그리고 표시해둔 값에서 -와 +계산을 한다

계산을 한 후 0미만 최대 볼륨의 값 초과 일때는 표시하지 않는다

그렇게 계속 이동하면된다.