[Toss 2024 Next 2번 유사 문제] 앱

[uijin-j]

🔗 앱

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.*; import java.io.*; /** * 15:24 START 16:09 END (45분) */ public class Main { /** * N개의 앱이 있음 (N은 최대 100) * 각 앱은 m1 m2 .. mn 메모리를 차지하고 있음 (해당 앱을 제거했을 때 이득) * 각 앱은 c1 c2 .. cn 의 재시작 시간이 걸림 (해당 앱을 제거했을 때 손실) * * 적절하게 앱을 선택해서 최소 손실로 M 이상의 메모리를 확보하자. * * 풀이. 이득과 손실이 있기 때문에 배낭 문제? * - but 같은 앱을 여러 개 선택 X (토스랑 다른 점) * - 딱 M이 아니라 M 이상을 맞추면 됨 */ public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); int n = Integer.valueOf(st.nextToken()); int m = Integer.valueOf(st.nextToken()); int[] memory = new int[n]; st = new StringTokenizer(bf.readLine()); for(int i = 0; i < n; ++i) memory[i] = Integer.valueOf(st.nextToken()); int[] cost = new int[n]; st = new StringTokenizer(bf.readLine()); for(int i = 0; i < n; ++i) cost[i] = Integer.valueOf(st.nextToken()); int[] dp = new int[m+1]; // dp[i]는 i 메모리를 확보하기 위한 최소 비용 Arrays.fill(dp, 10001); // 앱이 최대 100개이고, 각 앱의 비용이 최대 100이기 때문에 최댓값은 10_000 dp[0] = 0; for(int app = 0; app < n; ++app) { int appMemory = Math.min(memory[app], m); int appCost = cost[app]; for(int mem = m + appMemory; mem >= appMemory; --mem) { // 조건 1. 같은 앱을 여러 개 선택 X 이기 때문에 거꾸로! // 조건 2. 딱 M을 맞추는 것이 아니라서 M + appMemory 부터 시작 int idx = Math.min(mem, m); dp[idx] = Math.min(dp[idx], appCost + dp[mem - appMemory]); } } System.out.println(dp[m]); } } ```

코멘트

- 어제 풀어서 그런지.. 조금 고민하면 풀 수 있는 문제였네요.. 어젠 왜 못 풀었을까요😢
- 주석처리 한 것처럼 일반적인 냅색과 다른 부분을 적절하게 처리해주면 되는 문제였습니다! (다른점 1. 같은 앱을 여러 개 선택할 수 없음 / 다른점 2. 딱 M이 아니라 M이상을 만족시키면 됨)

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include using namespace std; //10:32 int n,m; pairnum[100]; // 메모리, 비용 long long dp[10001]; //100*100 long long sumN; int main() { cin>>n>>m; for(int i=0;i>num[i].first; } for(int i=0;i>num[i].second; sumN += num[i].second; } for(int i=0;i=num[i].second;j--){ dp[j] = max(dp[j], dp[j-num[i].second] +num[i].first); } } int ansT=0,ans=0; int i=0; while(true){ if(dp[i++]>=m){ ans = i; break; } } cout<

코멘트

- 3달전에 풀었는데도 좀 고민한 부분이 있네요.. dp 공부 더 해야겠습니다.