본문 바로가기

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

 (15)
뮤탈리스크 www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net #include #include #include #define INF 999999999 using namespace std; int dp[70][70][70]; int n, a, b, c; int func(int x, int y, int z) { if (!x&&!y&&!z)return 0; int &ret = dp[x][y][z]; if (ret != -1)return ret; ret = INF; ret = min(re..
평범한 배낭 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net #include #include #include #include using namespace std; int arr[101][100001]; int main() { int n; int weight; cin >> n; cin >> weight; memset(arr, 0, sizeof(arr)); vectorthings(100); for (int i..
파일 합치기 www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net #include #include int INF = 1000000007; using namespace std; int dp[501][501]; int cost[501]; int sum[501]; int T, K, i; int main() { cin >> T; while (T--) { cin >> K; for (i = 1; i > cost[i]; sum[i] = sum[i - 1] + cost[i]; } ..
1,2,3 더하기 4 www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net #include #include #include using namespace std; int dp[10001][4]; void solve(int n, int k) { if (dp[n][k]) { return; } for (int i = 4; i > num; solve(num,3); answer.push_back( dp[num][1] + dp[num]..
팰린드롬? www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net #include #include #include using namespace std; int check[2002][2002]; bool toggle = false; int find(int *arr, int s, int f) { if (s == f) { return 1; } else { if (check[s][f] != -1) { return check[s][f]; } if (s + 1 == f && arr[s] == arr[f]) { return 1..
점프점프 www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net #include #include using namespace std; int main() { int n; int check[1001] = { 0, }; check[1] = 1; cin >> n; int num; for (int i = 1; i >num ; if (check[i] == 0) continue; for (int j = 1; (j
이동하기 www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net #include #include #include using namespace std; int candymap[1001][1001]; int check[1001][1001]; int main() { int n; int m; cin >> n; cin >> m; memset(candymap, 0, sizeof(candymap)); memset(candymap, 0, sizeof(check)); for ..

티스토리툴바