알고리즘/BFS
[백준] 2073-수도배관공사(C++)
잉읭응
2021. 5. 28. 16:10
반응형
문제링크: https://www.acmicpc.net/problem/2073
2073번: 수도배관공사
아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7<=D<=100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다.
www.acmicpc.net
전형적인 dp문제
접근방식
1. dp를 사용해서 문제를 해결
dp[n] = max(dp[n], cost)
만약 이전 dp값과 합칠 수 있다면 --- temp = min(dp2[j - arr[i][0]], arr[i][1])
dp[j] = max(dp[j], temp);
2. 메모리가 생각보다 크다. 이차원 배열로 풀지 말고 before dp 배열을 하나 만들어서 이전 값과 비교해주면서 진행!
문제풀이
1. dp!
2. 두 점화식을 구현!
아래는 정답코드입니다.
#include <iostream>
#include <algorithm>
using namespace std;
int d, p;
int dp[100001];
int dp2[100001];
int arr[351][2];
int temp = 0;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> d >> p;
for (int i = 1; i <= p; i++)
cin >> arr[i][0] >> arr[i][1];
for (int i = 1; i <= p; i++) {
for (int j = 1; j <= d; j++) {
if (j == arr[i][0])
dp[j] = max(dp[j], arr[i][1]);
if (j > arr[i][0]) {
if (dp2[j - arr[i][0]] != 0) {
temp = min(dp2[j - arr[i][0]], arr[i][1]);
dp[j] = max(dp[j], temp);
}
}
}
for (int j = 1; j <= d; j++) {
//cout << dp[j] << ' ';
dp2[j] = dp[j];
}
//cout << endl;
}
cout << dp[d] << endl;
return 0;
}
반응형