본문 바로가기

백준/다이나믹 프로그래밍

(15)
다리놓기 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net #include #include #include using namespace std; int n, m,t; long long com[30][30]; // nCr 구하기 int combi(int n, int r) { if (n == r) { return 1; } if (r == 0 || n == 0) { return 1; } if (com[n][r] != 0) { return com[n][r]; } return ..
성냥깨비 www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net #include #include #include #include #include using namespace std; long long num[9] = { 0, 0, 1, 7, 4, 2, 0, 8, 10 }; int main() { int n; cin >> n; int cnt; long long mindp[101]; long long maxdp[101]; mindp[0] = 0; mindp[1] = 0; mindp[2..
퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net #include #include #include #include using namespace std; int n; int dp[17]; int main() { cin >> n; memset(dp, 0, sizeof(dp)); vectort(n+2); //days vectorp(n+2); //profit for (int i = 1; i > t[i]; cin >> p[i]; } int ans = 0; for (int i = 1; i
우수 마을 / Tree DP www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net #include #include #include using namespace std; int n; int towns[10001]; vectorv(10001); int dp[10001][2]; bool visited[10001]; void dfs(int idx) { visited[idx] = true; dp[idx][0] = 0; dp[idx][1] = towns[idx]; for (int i = 0; ..
사회망 서비스 / Tree DP www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net #include #include #include using namespace std; int dp[1000001][2]; bool visited[1000001]; void dfs(vector&friends, int i) { visited[i] = true; dp[i][0] = 0; dp[i][1] = 1; for (int j = 0; j < friends[i].size(); j++) { if (visite..
LCS www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #include #include #include #include #include using namespace std; int dp[1001][1001]; int main() { string str; string str2; cin >> str; cin >> str2; int strl = str.size(); int strl2 = str2.size(); memset(dp..
새로운 게임 www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net #include #include using namespace std; struct horse { int x, y, d; bool is_bottom; } h[10]; int N, K; int dx[] = { 0, 0, 0, -1, 1 }; int dy[] = { 0, 1, -1, 0, 0 }; int turn[] = { 0, 2, 1, 4, 3 }; int color[13][13]; vector info[13][..
기타리스트 www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net #include #include using namespace std; int main() { int v[100]; bool dp[101][1001]; int n, s, m; memset(dp, false, sizeof(dp)); cin >> n >> s >> m; for (int i = 0; i > v[i]; } dp[0][s] = true; ..