경우없는 개발 블로그

https://www.acmicpc.net/status?user_id=dfdfg1&problem_id=21610&from_mine=1

#문제 간단 정리

문제 그대로 잘 따라가기만 하면 되는 구현문제이다

다만 구현을 하면서 나름 주의해야 될 점들이 있으니 주의하자.

#문제 해결 방법

우선 구현해야될건

구름 이동함수 move

그리고 경계 처리를 위한 isBoundary 함수

물 복사 함수 makeWater

구름 생성 함수 makeCloud

그리고 순서에 따라서

구름 이동하기 -> 물 복사 -> 구름생성

을 구현한 함수를 차례대로 실행시켜주면 된다.

여기서 구름은 isCloud 2중 벡터로 추적하는데 주의해야 될점은

void move(int d, int s) {
    vector<vector<bool>> tempCloud(N + 1, vector<bool>(N + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (isCloud[i][j]) { 
                int ny = isBoundary(i + (s * dy[d - 1]));
                int nx = isBoundary(j + (s * dx[d - 1]));  

                tempCloud[ny][nx] = true; 
                mapVec[ny][nx] += 1;   
            }
        }
    }

    isCloud = tempCloud;  
}

여기서 처럼 temCloud 배열을 전부 false 로 선언한 후에

isCloud 를 이용하여 이동한 구름들을 기록하고

이 이동한 구름을

isCloud = tempCloud;

이런식으로 복사함으로써

기존의 isCloud 배열을 사용한후 이동한 기록을 복사함으로

구름의 이동을 구현 할 수 있다.

makeCloud 함수 구현도 같은 방식을 사용하고.

또 하나 주의해야 될 점은 구름 이동과 물 복사시에

경계처리를 주의하도록하자

N 다음에 1 이 오도록 경계를 확인하는

isBoundary 함수도 구현하는 것도 잊지 않는다면 무난하게 구현 가능하

#전체 코드

#include <iostream>
#include <stack>
#include <cctype> 
#include <vector>
#include <queue>

using namespace std;

int N, M;
//구름이동
int dx[8] = {-1,-1,0,1,1,1,0,-1}; 
int dy[8] = {0,-1,-1,-1,0,1,1,1};

//대각선 확인
int ddx[4] = {-1,1,-1,1};
int ddy[4] = {-1,-1,1,1};

vector<vector<int>> mapVec;
vector<vector<bool>> isCloud;

//원형으로 이어주기 위한 확인함수
int isBoundary(int x) {
    if (x > N) {
        x = x%N;
    }
    
    if (x < 1) {
        x = N + (x % N);
    }

    return x;
}
void move(int d, int s) {
    vector<vector<bool>> tempCloud(N + 1, vector<bool>(N + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (isCloud[i][j]) { 
                int ny = isBoundary(i + (s * dy[d - 1]));
                int nx = isBoundary(j + (s * dx[d - 1]));  

                tempCloud[ny][nx] = true; 
                mapVec[ny][nx] += 1;   
            }
        }
    }

    isCloud = tempCloud;  
}

void waterCopy() {

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {

            if (isCloud[i][j]) {
                int count = 0;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = j + ddx[dir], ny = i + ddy[dir];
                    if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && mapVec[ny][nx] > 0) {
                        count++;
                    }
                }
                mapVec[i][j] += count;
            }
        }
    }


}

void makeCloud() {
    vector<vector<bool>> newCloud(N + 1, vector<bool>(N + 1, false));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (!isCloud[i][j] && mapVec[i][j] >= 2) {
                newCloud[i][j] = true;
                mapVec[i][j] -= 2;
            }
        }
    }
    isCloud = newCloud;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;


    mapVec.resize(N+1, vector<int>(N + 1, 0));
    isCloud.resize(N + 1, vector<bool>(N + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> mapVec[i][j];
        }
    }

    isCloud[N][1] = true;
    isCloud[N][2] = true;
    isCloud[N-1][1] = true;
    isCloud[N-1][2] = true;
   
    for (int i = 0; i < M; i++) {
        int d, s;
        cin >> d >> s;

        move(d, s);
        waterCopy();
        makeCloud();
    }

    //물 합산
    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {  
            result += mapVec[i][j];
        }
    }

    cout << result << '\n';

    return 0;
}

https://www.acmicpc.net/problem/18870

#문제 간단 정리

#문제 해결 방법

인덱스 추적을 위해서 pair < 값 ,인덱스 > 로 받고

원소들을 정렬 후에

순서를 추적하기 위해 rank 변수 선언 후에

정렬된 값이 이전 값과 같다면 rank를 증가하지 않고

다르다면 rank를 증가한다

그리고 추적한 인덱스에 rank 값을 넣어주면 된다.

#전체 코드

#include <iostream>
#include <stack>
#include <cctype> 
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<pair<int,int>> inputs(n);

    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        inputs[i] = { input,i };
    }
    sort(inputs.begin(), inputs.end());


    vector<int> index(n);
    int rank = 0; 
    int last = INT_MIN; 

   
    for (int i = 0; i < n; i++) {
        if (i != 0 && inputs[i].first != inputs[i - 1].first) {
            rank ++;
        }
        index[inputs[i].second] = rank; 
        last = inputs[i].first; 
    }

    for (int k : index) {
        cout << k << ' ';
    }

    return 0;
}

https://www.acmicpc.net/problem/2665

#문제 간단 정리

다익스트라 문제

이전에 풀었던 알고스팟

https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EC%8A%A4%ED%8C%9F-1261%EB%B2%88

에서 벽을 0으로 변경하기만 하면된다

둘이 로직이 같기때문에 참고하자

#문제 해결 방법

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

vector<vector<int>> maze;
vector<vector<int>> cost;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    maze.resize(n, vector<int>(n, 0));
    cost.resize(n, vector<int>(n, INF));

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            maze[i][j] = s[j] - '0';
        }
    }

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    pq.push({0, {0, 0}});
    cost[0][0] = 0;

    while (!pq.empty()) {
        int currentCost = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        if (x == n - 1 && y == n - 1) {
            cout << currentCost << '\n';
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                int nextCost = currentCost + (maze[nx][ny] == 1 ? 0 : 1);
                if (nextCost < cost[nx][ny]) {
                    cost[nx][ny] = nextCost;
                    pq.push({nextCost, {nx, ny}});
                }
            }
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/1261

#문제 간단 정리

다익스트라를 활용하자

#문제 해결 방법

벽을 부수는건 1 코스트가 들기 때문에

벽을 부수는 걸 우선으로 하는 우선순위 큐를 활용해서

bfs 를 사용 (다익스트라)

해서 문제를 풀면 된다

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

vector<vector<int>> maze;
vector<vector<int>> cost;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> m >> n;

    maze.resize(n, vector<int>(m, 0));
    cost.resize(n, vector<int>(m, INF));

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            maze[i][j] = s[j] - '0';
        }
    }

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    pq.push({0, {0, 0}});
    cost[0][0] = 0;

    while (!pq.empty()) {
        int currentCost = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        if (x == n - 1 && y == m - 1) {
            cout << currentCost << '\n';
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                int nextCost = currentCost + (maze[nx][ny] == 1 ? 1 : 0);
                if (nextCost < cost[nx][ny]) {
                    cost[nx][ny] = nextCost;
                    pq.push({nextCost, {nx, ny}});
                }
            }
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/1584

#문제 간단 정리

0-1 bfs 문제

#문제 해결 방법

기존의 bfs 에서 

비용이 들지 않는 것을 먼저 우선순위를 두어 계산해주는 

0-1 bfs 를 활용하자

덱을 사용해서 

생명소모없이 지나갈 수 있는 안전지대를

덱의 앞으로 푸쉬하고

생명소모하는 위험지대를 

덱의 뒤로 푸쉬해서

우선순위에 차이를 둬서 탐색하도록 하면 된다

또한 주의해야될게 각 모서리 두 부분이 주어지는데

모서리에 따른 위험지대 처리에 주의하도록 하자

어느쪽에 있는 모서리인지 확인해야 한다

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <deque>
using namespace std;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

void zoneSetting(vector<vector<int>>& zone, int y1, int y2, int x1, int x2, int type) {
    for (int i = min(y1, y2); i <= max(y1, y2); i++) {  
        for (int j = min(x1, x2); j <= max(x1, x2); j++) {
            zone[i][j] = type;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //0 안전 1 위험 2 죽음
    vector<vector<int>> zone(501, vector<int>(501, 0));
    vector<vector<bool>> visited(501, vector<bool>(501, false));

    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x1, y1, x2, y2;
        cin >> x2 >> y1 >> x1 >> y2;
        zoneSetting(zone, y1, y2, x1, x2, 1);
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int x1, y1, x2, y2;
        cin >> x2 >> y1 >> x1 >> y2;
        zoneSetting(zone, y1, y2, x1, x2, 2);
    }

    deque<pair<pair<int, int> , int>> d;
    d.push_back({ { 0, 0 } , 0 });
    visited[0][0] = true;
    int goalLife = 0;
    bool goal = false;

    while (!d.empty()) {
        int bx = d.front().first.first;
        int by = d.front().first.second;
        int life = d.front().second;
        if (bx == 500 && by == 500) {
            goal = true;
            goalLife = life;
            break;
        }

        d.pop_front();

        for (int i = 0; i < 4; i++) {
            int nx = bx + dx[i];
            int ny = by + dy[i];

            if (0 <= nx && nx <= 500 && 0 <= ny && ny <= 500 && !visited[nx][ny]) {
                visited[nx][ny] = true; 
                if (zone[nx][ny] == 0) {
                    d.push_front({ { nx, ny }, life });
                }
                else if (zone[nx][ny] == 1) {
                    d.push_back({ { nx, ny },life +1});
                }
            }
        }
    }

    if (goal) {
        cout << goalLife << '\n';
    }
    else {
        cout << -1 << '\n';
    }


    return 0;
}

https://www.acmicpc.net/problem/6126

#문제 간단 정리

일종의 배낭문제 

#문제 해결 방법

dp[i] = 금액을 만들 수 있는 가지수 

즉 dp[i] = dp[i-coin들의 종류] 를 해주면 된다

여기서 주의할것은 코인을 1+2 와 2+1 는 중복되는 것이기 때문에 이를 고려해 주어야 한다

for (int i = 1; i <= N; i++) {
        for (auto coin : coins) {
            if (i - coin >= 0) {
                dp[i] += dp[i - coin];
            }
        }
    }

이렇게 써버리면 순서에 따라서 중복이 나오고 

  for (auto coin : coins) {
      for (int i = coin; i <= N; i++) {
          dp[i] += dp[i - coin];
      }
  }이렇게 써서 중복이 안나오도록 

작은 순서부터 코인을 쓰도록 해야 중복을 피할 수 있다.

 #전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
#include <tuple>
#include <sstream>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int V, N;
    cin >> V >> N;
    vector<int> coins(V);
    vector<int> dp(N+1, 0);
    dp[0] = 1;
    for (int i = 0; i < V; i++) {
        cin >> coins[i];
    }

    //dp[i] i금액을 만들 수 있는 가짓수 / dp[i] = dp[i-coins]

 /*   for (int i = 1; i <= N; i++) {
        for (auto coin : coins) {
            if (i - coin >= 0) {
                dp[i] += dp[i - coin];
            }
        }
    }*/
    for (auto coin : coins) {
        for (int i = coin; i <= N; i++) {
            dp[i] += dp[i - coin];
        }
    }


    cout << dp[N] << '\n';
         
    return 0;
}

https://www.acmicpc.net/problem/4949

#문제 간단 정리

흔한 괄호문제의 응용

스택을 활용한다.

#문제 해결 방법

스택을 활용해 괄호일 경우 스택에 넣어주고 

같은 괄호일경우에 pop 

비어있는 경우나 괄호가 닫는괄호가 아닐경우 오답으로 간주,

수많은 스택 활용 괄호 문제중에 하나이다.

getline 으로 한줄 전체를 읽어오는 것을 활용하자

그리고 가독성좀 생각해야겠다..

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <map>
#include <string>
using namespace std;



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<string> lines;
    vector<bool> answers;

    while (true) {
        string input;
        getline(cin, input);

        if (input == ".") {
            break;
        }

        vector<char> brackets;
        bool flag = true;

        for (int i = 0; i < input.size(); i++) {

            if (input[i] == '(') {
                brackets.push_back('(');
            }
            else if (input[i] == ')') {
                if (brackets.empty()) {
                    flag = false;
                    break;
                }
                else if (brackets.back() == '(') {
                    brackets.pop_back();
                }
                else if (brackets.back() != '(') {
                    flag = false;
                    break;
                }
            }
            else if (input[i] == '[') {
                brackets.push_back('[');
            }
            else if (input[i] == ']') {
                if (brackets.empty()) {
                    flag = false;
                    break;
                }
                else if (brackets.back() == '[') {
                    brackets.pop_back();
                }
                else if (brackets.back() != '[') {
                    flag = false;
                    break;
                }
            }

        }
        
        if (!brackets.empty()) {
            flag = false;
        }

        if (flag) {
            answers.push_back(true);
        }
        else {
            answers.push_back(false);
        }
    }

    for (bool a : answers) {
        if (a == true) {
            cout << "yes" << '\n';
        }
        else {
            cout << "no" << '\n';
        }
    }


    return 0;
}

리팩토링한 코드

#include <iostream>
#include <vector>
#include <map>
using namespace std;

// 괄호의 짝을 확인하는 함수
bool isValidBracketSequence(const string& input) {
    vector<char> stack;
    map<char, char> bracketPairs = {{')', '('}, {']', '['}};
    
    for (char ch : input) {
        if (ch == '(' || ch == '[') {
            stack.push_back(ch);
        } else if (ch == ')' || ch == ']') {
            if (stack.empty() || stack.back() != bracketPairs[ch]) {
                return false;
            }
            stack.pop_back();
        }
    }
    return stack.empty();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<bool> answers;
    string input;

    while (true) {
        getline(cin, input);
        if (input == ".") break;

        answers.push_back(isValidBracketSequence(input));
    }

    for (bool isValid : answers) {
        cout << (isValid ? "yes" : "no") << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/2357

#문제 간단 정리

세그먼트 트리를 활용하자

#문제 해결 방법

기본적으로 a b 구간에서 최솟값과 최댓값을 구한다면 

ab 전체를 훑도록 구현할 수 있는데 이는 

시간 초과가 나는게 자명하다.

때문에 세그먼트 트리를 활용해서 빠르게 구해주도록 하자

우선 세그먼트 트리에 대한 지식이 있다고 가정하고 설명하자면

최솟값을 저장하는 트리와

최댓값을 저장하는 트리를 만들어서

구간에 대한 최솟값과 최댓값을 저장하게 만들어 

각 쿼리에 대한 답을 logN 의 시간으로 구한다.

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
#include <tuple>
#include <sstream>
#include <map>
#include <climits>
using namespace std;

vector<int> arr;
vector<int> treeMin; 
vector<int> treeMax;


// 세그먼트 트리 초기화 함수
int initMin(int start, int end, int index) {
    if (start == end) {
        treeMin[index] = arr[start];
        return treeMin[index];
    }
    int mid = (start + end) / 2;

    treeMin[index] = min( initMin(start, mid, index * 2) , initMin(mid + 1, end, index * 2 + 1));
    return treeMin[index];
}

int findMin(int start, int end, int index, int left, int right) {

    if (left > end || right < start) {
        return INT_MAX;
    }

    if (left <= start && end <= right) {
        return treeMin[index];
    }

    int mid = (start + end) / 2;

    return min(findMin(start, mid, index * 2, left, right) , findMin(mid + 1, end, index * 2 + 1, left, right));
}

int initMax(int start, int end, int index) {
    if (start == end) {
        treeMax[index] = arr[start];
        return treeMax[index];
    }
    int mid = (start + end) / 2;

    treeMax[index] = max(initMax(start, mid, index * 2), initMax(mid + 1, end, index * 2 + 1));
    return treeMax[index];
}

int findMax(int start, int end, int index, int left, int right) {

    if (left > end || right < start) {
        return INT_MIN;
    }

    if (left <= start && end <= right) {
        return treeMax[index];
    }

    int mid = (start + end) / 2;

    return max(findMax(start, mid, index * 2, left, right), findMax(mid + 1, end, index * 2 + 1, left, right));
}

int main() {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N ,M;
    cin >> N;
    cin >> M;
    arr.resize(N+1);
    treeMin.resize(4 * N); 
    treeMax.resize(4 * N);

    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    initMin(1, N, 1); 
    initMax(1, N, 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        cout << findMin(1, N, 1, a, b) << " " << findMax(1, N, 1, a, b) << "\n";
    }

  

    return 0;
}

https://www.acmicpc.net/problem/1920

#문제 간단 정리

명백히 이분탐색으로 푸는 문제

#문제 해결 방법

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;

int binarySearch(vector<int> &vec, int target) {

    int start = 0;
    int end = vec.size()-1;


    while (start <= end) {

        int mid = (start + end) / 2;

        if (vec[mid] == target) {
            return 1;
        }
        else if (vec[mid] > target) {
            end = mid - 1;
        }
        else if (vec[mid] < target) {
            start = mid + 1;
        }
    }

    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    vector<int> vec(N);

    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    int M;
    cin >> M;
    vector<int> vec2(M);
    for (int i = 0; i < M; i++) {
        cin >> vec2[i];
    }


    for (auto o : vec2) {
        cout <<  binarySearch(vec, o)<<'\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/7579

#문제 간단 정리

일단 배낭문제이다.

기존의 가방문제는 최소 무게를써서 최대 가치를 찾고

최대 가치를 가진 마지막 dp 배열이 정답이였다면

이 문제는 최소 비용으로 최대메모리를 찾고 그중에서 그 메모리이상의 첫번쨰 dp 배열을 찾는다는게 차이점

#문제 해결 방법

DP 배열을 dp[i][j]로 정의하고, 이를 "처음부터 i번째 앱까지 고려했을 때, 비활성화의 총 비용이 j일 때 확보할 수 있는 메모리의 최대량"으로 정의

즉 기존의 가방문제처럼 현재 비용(j)으로 구할수 있는 최대 메모리 dp[i][j]를 갱신한 후에

첫번째로 오는 M을 넘는 메모리를 가진 j(비용) 의 인덱스가 찾는 정답이다

쉽게 말하자면 dp 배열에는 순차적으로 j의 비용을 써서 얻는 최대 메모리가 저장되어있고

소비 j가 작으면서 M을 넘는 메모리의 허용량을 앞의 인덱스(작은j)부터 찾으면

즉 비용을 통해 최대 메모리를 가지도록 dp를 구현하고 최소 비용으로 목표 메리를 넘는 비용을 확인해 주면

된다는점이 기존 배낭문제랑 다르다.

#전체 코드

2차원 dp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll N, M;
    cin >> N >> M;

    vector<ll> m(N), c(N);
    for (ll& memory : m) cin >> memory;
    for (ll& cost : c) cin >> cost;

    ll sumCost = 0; // 가능한 최대 비용의 합
    for (int i = 0; i < N; i++) sumCost += c[i];

    vector<vector<ll>> dp(N+1, vector<ll>(sumCost+1, 0));

    // DP를 이용해 해결
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= sumCost; j++) {
            // 현재 앱 i를 비활성화하지 않는 경우
            dp[i][j] = dp[i-1][j];
            // 현재 앱 i를 비활성화할 수 있고, 그러기 위한 비용이 충분한 경우
            if (j >= c[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-c[i-1]] + m[i-1]);
            }
        }
    }

    // 필요한 메모리 M 바이트를 확보하기 위한 최소 비용 찾기
    ll answer = sumCost;
    for (int j = 0; j <= sumCost; j++) {
        if (dp[N][j] >= M) {
            answer = j;
            break;
        }
    }

    cout << answer << endl;

    return 0;
}

1차원dp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll N, M;
    cin >> N >> M;

    vector<ll> memory(N), cost(N);

    for (int i = 0; i < N; i++) {
        cin >> memory[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> cost[i];
    }

    ll maxCost = 100 * N; // 최대 비용
    vector<ll> dp(maxCost+1, 0); // 비용에 따른 메모리 최대치 저장

    for (int i = 0; i < N; i++) {
        for (int j = maxCost; j >= cost[i]; j--) {
            dp[j] = max(dp[j], dp[j-cost[i]] + memory[i]);
        }
    }

    // 필요한 메모리 M 바이트를 확보하기 위한 최소 비용을 찾기
    ll answer = maxCost;
    for (int i = 0; i <= maxCost; i++) {
        if (dp[i] >= M) {
            answer = i;
            break;
        }
    }

    cout << answer << endl;

    return 0;
}