BOJ - 7579번 앱(C++)

문제 출처: https://www.acmicpc.net/problem/7579

문제 난이도

Gold 3

문제 접근법

처음에 문제를 이해를 잘못해서 투포인트로 풀었다. 냅색 알고리즘으로 접근한다. 이 때, 걍 dp로 풀어도 되고 메모제이션(DFS)로 풀어도 좋다.
여기서 주의할 게 memory로 두고 dp[M]일 때, 최소 코인을 출력할 수 있는데 M 범위가 1억이기 때문에 cost로 dp를 따져야한다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int cost[101];
int memory[101];
int dp[101][10001];
int N, M;

int dfs(int idx, int sumC) {
	if (idx >= 100) return 0;
	if (dp[idx][sumC] != -1) return dp[idx][sumC];
	dp[idx][sumC] = dfs(idx + 1, sumC);
	if(cost[idx] <= sumC) dp[idx][sumC] = max(dp[idx][sumC], memory[idx]+dfs(idx + 1, sumC - cost[idx]));
	return dp[idx][sumC];
}


int main() {
	memset(dp, -1, sizeof(dp));
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> memory[i];
	for (int i = 0; i < N; i++) cin >> cost[i];

	int totalC = 0;
	while (1) {
		if (dfs(0, totalC) >= M) {
			break;
		}
		totalC++;
	}
	cout << totalC << "\n";
	return 0;
}

피드백

냅색으로 하려다가 테케 통과도 안하는데 정답인게 이해가 안되서 다른식으로 풀었다. 그러다 다른 사람 코드를 참고하게 됐는데 첨에 메모제이션 때 0으로 두고 했는데 값이 안나오길래 고전했다. 메모제이션 때 -1로 초기화안해도 충분히 값이 나왔기 때문이었는데 이 문제 같은 경우는 0도 값에 포함이 되기 때문에 -1로 초기화해서 풀어야 됐다.
그래서 int ans =0;으로 두고 푸는 것보다 dp[idx][sumC]로 걍 바로 접근하게 했다.

이 문제는 시간이 지나고 다시 풀어봐야겠다. 문제 이해하는데도 오래걸렸고 접근법을 생각해내는게 좀 어려웠다.