7570 c++2 BOJ 7579 - 앱 https://www.acmicpc.net/problem/7579 접근앱 중 최소비용으로 최대의 메모리를 확보하는 문제이다.휴대폰 메모리 M이 정해져있기 때문에, 냅색 문제로 해결할 수 있다.냅색 문제에서 weight와 value는 각각 앱의 비용과 앱의 메모리를 의미한다. 기존 냅색 문제에서 DP[i][j]의 의미는 i번째 앱 시점에서 j의 코스트로 가지는 최대 메모리 사용량이다.이중for문을 돌면서 DP[i][j]를 구하면된다. 그리고 마지막에 DP[i][j]가 M이상인 것 중 첫번째가 답이 된다.왜냐하면 i번째를 살펴볼때 j가 0부터 total(사용할 수 있는 최대 코스트)까지를 살피는 경우는 i번째 앱이 포함될 수도 있고 아닐 수도 있기 때문이다. 코드#include #include #inclu.. 2024. 7. 12. [그리디 #21] BOJ 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1차 시도 처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다. 1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다. 2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다. 그러나 이것은 금방 틀리다는 것을 알 수 있다. 가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다. 따라서, 순서를 집중해서 공략하는게 좋겠다고 .. 2024. 2. 27. 이전 1 다음
