알고리즘/백준 (16) 썸네일형 리스트형 백준 12865번 평범한 배낭 C/C++ 풀이 https://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 가장 고전적인 DP 문제 예전에는 DP를 점화식으로만 이해했었는데, 2차원 배열로 이해하고 나니 더 깊은 이해를 할 수 있게 되는 것 같다. https://gsmesie692.tistory.com/113 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다... 백준 15486번 퇴사2 C/C++ 풀이 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 역시도 DP 문제 1부터 n까지 순회하면서 현재까지의 최댓값을 저장해둔다. dp[n]은 n일까지 일했을 때 얻을 수 있는 최대 수익으로 i번째 날에 들렸을 때, 현재까지 얻을 수 있는 최댓값과 그 날에 저장된 값을 비교하여 갱신하여 주고, i번째 날에 일했을 때 얻을 수 있는 최대 수익을 i번째 일했을 때 수익을 얻는 날(i + 해당 일의 소요 날짜) dp 배열에.. 백준 2228번 구간 나누기 C/C++ 풀이 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 �� www.acmicpc.net 이 역시 DP로 푸는 문제. 점화식을 dp[n][m](n개를 m개의 구간으로 나눴을 때의 최댓값) = dp[n-1][m](n을 포함하지 않고 m개를 선택했을 때의 최대값) 이거나 sum(i부터 n까지의 합) + dp[i - 2](하나의 공백이 있어야하기 때문에 i-2부터)[m-1](구간 하나 줄어들었으니 m-1로)' 으로 나타낼 수 있다. #include #include usi.. 백준 5535번 패셔니스타 C/C++ 풀이 https://www.acmicpc.net/problem/5535 DP 문제 전의 선택한 옷의 화려함 정도와 현재의 날짜를 요소로 두고 동적계획법을 사용하였다. 어렵지 않기 때문에 나머지는 코드로 설명 #include #include #include #include using namespace std; #define MAX 201 FILE* in = fopen("input.txt", "r"); int n, d; int tmp[MAX]; int min_tmp[MAX]; int max_tmp[MAX]; int cool[MAX]; int cache[101][MAX]; //재귀를 사용한 DP int dp(int coolness, int day) { //d 날짜가 됐다면 return if (day == d) re.. 백준 2240번 자두나무 C/C++ 풀이 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net DP 문제이다. DP는 메모이제이션을 위해 어떤 요소들을 저장할지가 가장 중요한데, 해당 문제에서는 3가지를 꼽을 수 있다. 현재 나의 위치, 현재 시각, 이동한 횟수 이에 따라서 현재 나의 위치와 떨어지는 자두의 위치에 따라 크게 4가지 선택이 가능한데, If(현재 나의 위치에서 자두가 떨어진다면) { 1. 현재 위치에서 움직이지 않고 자두를 먹는다 2. 현재 위치에서 움직이고 다음턴의 반전을 노려본다... 백준 5557번 1학년 C/C++ 풀이 https://www.acmicpc.net/problem/5557 DP 문제. 해당 idx에 어떤 sum을 가지고 있는가를 저장해나가며 함수를 진행시켜나간다. 계산 중간에 0~20을 넘어가는 경우 더이상 진행하지 않기 때문에 이를 저장하지 않는다. #include #include #define MAX 101 FILE* in = fopen("input.txt", "r"); int n; int array[MAX]; long long int cnt; long long int cache[MAX][21]; int dst; //재귀로 구현한 dp long long int dp(int idx, int sum) { //계산 값이 범위를 벗어나는 경우 return if (sum 20) return.. 백준 1633번 최고의 팀 만들기 C/C++ 풀이 https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 문제 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 �� www.acmicpc.net 전형적인 동적계획법 문제. 재귀함수와 메모이제이션을 이용해서 문제를 풀었다. #include #include #include using namespace std; FILE* in = fopen("input.txt", "r"); int white[1001]; int black[1001]; int cache[1001][16][16]; int n; int dp(int w, int b, int.. 백준 14502번 연구소 C/C++ 풀이 acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제에서 사용하는 범위의 크기가 크지 않아서 전체 map 안에서 벽과 바이러스가 없는 부분 재귀함수를 이용해서 3가지를 선택하고 그에 따라 안전 범위가 몇 개 생기는지를 구했다. #include #include using namespace std; FILE* in = stdin; #define MAX 8 int n, m; int map[MAX][MAX]; int cnt; int max = 0; int path[3]; bool c.. 이전 1 2 다음