목록백준/DP (47)
Study hard
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로 풀 수 있는 0-1 Knapsack문제였다. DP[i]: 용량이 i만큼 남았을 때 배낭에 넣을 수 있는 아이템 가치의 최댓값 점화식 if W[i] < K : DP[j] = max(DP[j], DP[j-W[i]]+V[i]) 지금까지의 용량 j일 때의 최댓값과 i번째 아이템을 추가 했을 때의 값을 비교 #include #include..
www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : i번째 장부터 j번째 장까지 어떤 순서로 합쳐야 최소비용이 나오는지(그 때의 최소비용) Sum[i] : 1장 ~ i장 비용 합 점화식 DP[i][[j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + Sum[j] - Sum[i-1]) (여기서 Sum[j] - Sum[i-1]은 i~j번째 장을 최종으로 합칠 때 드는 비용,..
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 [풀이] DP로 풀 수 있는 문제였다. 중복을 피하기 위해 오름차순으로만 더한다. DP[i][1]: 정수 i를 만들 때 1로 끝나는 경우 -> 그 이전에 1만 올 수 있다. DP[i][2]: 정수 i를 만들 때 2로 끝나는 경우 -> 그 이전에 1과 2가 올 수 있다. DP[i][3]: 정수 i를 만들 때 3으로 끝나는 경우 -> 그 이전에 1과 2..
acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [풀이] 팰린드롬이란 수열이 거꾸로 했을 때도 같은 수열인 경우를 말한다. 가장 작은 단위의 수열(1개)부터 범위를 늘리면서 팰린드롬 여부를 판단하는 DP를 사용하였다. DP[i][j]: S가 i이고 E가 j일 때 팰린드롬인지 여부 DP[i][i] = 1 if Num[i]==Num[j] : DP[i][i+1]=1 DP[i][j] = DP[i+1][j-1] && Num[i] == Num[j] ※cin, cout을 사용하면 시간초과가 나므로 scanf, pri..
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 [풀이] 2020/09/14 - [백준/DP] - (c++)백준 14501번: 퇴사 (c++)백준 14501번: 퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을.. nim..
www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을 수 있는 이익 상담이 끝나는 날이 N+1보다 커지면 무시한다. #include #include //max using namespace std; int N; int T[16]; int P[16]; int DP[16] = { 0, }; void solution() { int ans = 0; for (int i = N; i >= 1; i--) { //상담이 끝나는 날이 N+1보다 크면 if (i + T[i] > N + 1) continue; else { in..