와이유스토리

https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net #include #include #include #define MAX 10001 using namespace std; int n, a, b, ans; int dp[MAX][2]; int visited[MAX]; int check[MAX]; vector w; vector v[MAX]; vector tree[MAX]; vector r; void dfs(int x) { ..

https://www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net #include #include #define MAX 10005 using namespace std; int num, a, b, ans; int dp[MAX][2]; int visited[MAX]; int people[MAX]; vector tree[MAX]; // 배열, 리스트 void calSubTree(int n) { // n이 루트인 subtree dp 계산 for (..

https://www.acmicpc.net/problem/2180 #include #include #include #define MAX 100001 using namespace std; int n ,a, b; int ans; vector v; bool cmp(pair p, pair q) { int a = p.first, b = p.second, c = q.first, d = q.second; if (a == 0) return false; else if (c == 0) return true; else if ((b == 0) && (d == 0)) return a < c; return b * c < a * d; } int main() { ios_base::sync_with_stdio(0); cin.tie(0..

https://www.acmicpc.net/problem/14908 #include #include #include #define INF 1234567891 #define MAX 11 using namespace std; int n, a, b, ans, sum; vector arr; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; for (int i = 0; i > a >> b; arr.push_back({ (double)b/a, n-(i+1) }); //first내림차순, second오름차순 } sort(arr.begin(), arr.end(), greater()); for (int..

https://www.acmicpc.net/problem/1757 #include #include #include #define MAX 1000001 using namespace std; int n, m, a; int dp[10001][501][2]; vector v; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; v.push_back(0); for (int i = 0; i > a; v.push_back(a); } for (int i = 1; i

※ 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ※ 풀이 동적계획법의 Bottom-Up방식으로 해결한다. dp[i]:=i를 1로 만들기 위한 최소 연산 횟수 1) i가 1일 때, 연산하지 않는다. (dp[1] = 0) 2) i가 2일 때, 2로 나눈다. (dp[2] = 1) 3) i가 3일 때, 3으로 나누다. (dp[3] = 1) 4) i가 4이상 일 때, - 6으로 나누어지면 dp[i/2]와 dp[i/3] 중 최소 연산 횟수에 1을 더한다. (dp[i]=min(dp[i/2], dp[i/3])+1) - 3으로 나누어지면 dp[i/3]에 1을 더한다..

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net #include #include #include #define MAX 1001 using namespace std; int n, w, a, b; int dp[MAX][MAX]; vector v1; vector v2; vector t; void calDp(int x, int y) { if ((x == w) || (y == w)) return; if (dp[x][y] != 0)..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net #include #include #define INF 1234567891 using namespace std; int n, m, a, ans=INF, sum; int dp[101][10001]; vector M; vector C; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; C.push_back(0);..