22.08.10. 풀었던 문제들

백준 단계별 24 DP 2

2293 동전 1

dp[k] : k원 만드는 경우의 수라고 생각하면, 점화식은 dp[i] = dp[i] + dp[i - coin[j]]이 된다.

 

7579 앱

 냅색 응용. 문제에서 주어진 대로라면 dp[i][j] = i번째 앱까지 봤을 때 memory j까지 사용했을 때 cost의 최솟값 이런 식으로 정의했겠지만, memory의 입력이 1천만, 앱의 종류가 100개기 때문에 두 개를 곱하면 1억이 넘어간다. 다른 방식으로 풀어야 한다.

 dp[i][j] = i번째 앱까지 봤을 때, cost j까지 사용했을 때 memory의 최댓값으로 생각하면 냅색과 같은 문제가 되고, "c - cost[a] >= 0 then dp[a-1][c-cost[a]] + memory[a]"의 점화식을 가지게 된다.

void solve(){
	int N, M; cin>>N>>M;
	vector<int> memories(N), costs(N);
	for(int &memory : memories) cin>>memory;
	for(int &cost : costs) cin>>cost;
 
	vector<vector<int>> dp(N+1, vector<int>(100*N+1, 0));
	// dp[i+1][j] : i번째까지 app, cost j을 사용해서 만들 수 있는 memory 최대값
	for(int a = 1; a<=N; a++){
		for(int c = 0; c<=100*N; c++){
			dp[a][c] = dp[a-1][c];
			if(c - costs[a-1] >= 0){
				dp[a][c] = max(dp[a][c], dp[a-1][c-costs[a-1]] + memories[a-1]);
			}
			// c - cost[a] >= 0 then dp[a-1][c-cost[a]] + memory[a]
		}
	}
 
	int min_cost = 99999999;
	for(int a = 1; a<=N; a++){
		for(int c = 0; c<=100*N; c++){
			if(dp[a][c] >= M) min_cost = min(min_cost, c);
		}
	}
	cout<<min_cost;
}

 

 

백준 단계별 25 graph and traversal

24479 알고리즘 수업 - DFS 1

 그냥 DFS 하면 되는 문제. DFS 코드 정립을 조금 해 보자.

int cnt = 1; 
vector<bool> visited;
vector<vector<int>> edges; // edges[i] : edge list starts from i
vector<int> visit_num;
 
void dfs(int cur_node){
	if(visited[cur_node]) return;
 
	visit_num[cur_node] = cnt++;
	visited[cur_node] = true;
	for(int adjacent : edges[cur_node]){
		if(!visited[adjacent]){
			dfs(adjacent);
		}
	}
}