작심 24/7

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com DP 너무 어려워.. #include #include #include #include using namespace std; int T, N, M; int arr[3002], brr[102]; int dp[3002][102][102][2]; // a, b 고른 수, b 버린 수, 가져가거나 안 가져가거나 int play(int a, int i, int j, int picked){ if (dp[a][i][j][picked] != -1) return dp[a][i][j][picked]; int val1 = 0, val2 = 0, val3 = 0, val4 = 0; if..

11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 � www.acmicpc.net 근우 입장에서 볼 때 근우 차례 : 점수가 더 높은 카드를 갖고 감으로써 점수를 최대로 하는 플레이를 해야 함 명우 차례 : 명우 입장에선 자신이 이기기 위해 점수가 더 높은 카드를 갖고 갈 것이므로 근우는 근우의 점수를 최소로 하는 플레이를 해야 함 DP[i][j] = i번째부터 j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수 근우 차례일 땐 점수를 최대로 해야 하므로 max(왼쪽 카드 + 왼쪽 카드를 뽑고 플레이한 결과, 오른쪽 카드 + 오른쪽 카드를 ..

16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 �� www.acmicpc.net 문자열 S를 처음부터 탐색하면서 현재 idx부터 목록 A에 있는 단어가 포함돼 있으면 재귀 호출로 (idx+단어 길이)번째부터 목록 A에 있는 단어가 있는지 탐색한다. 이때 dp[idx]가 true면 이전에 이 idx부터 시작되는 단어를 탐색해봤다는 뜻이므로 굳이 또 계산할 필요 없이 return으로 돌아온다. dp[idx]가 false면 처음 탐색한다는 뜻이므로 true로 바꿔주고 탐색하러 간다. idx와 문자열 S의 길이가 같다면 성..

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence) 문제이다. LCS(Longest Common Substring)과 같이 문자열 A, B에서 A[i]와 B[j]가 같을 때는 DP[i][j] = DP[i-1][j-1] + 1 이 되지만 A[i]와 B[j]가 다를 때는 DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + 1 이 된다. 그러면 최종적으로 DP[문자열A 끝][문자열B 끝]이 L..

5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예 www.acmicpc.net LCS(Longest Common Substring) 문제이다. 문자열 A, B에서 A[i]와 B[j]가 같을 때, DP[i][j] = DP[i-1][j-1] + 1 이 된다. 무슨 말이냐 하면 문자열 A는 ABCDE이고 B는 CDEGG라 할 때 예를 들어 A[4]과 B[2]가 E로 같으면 그 전까지의 문자열 ABCD와 CD에서 가장 길었던 문자열의 길이(DP[3][1])에 E 길이 1을 더한 값이 DP[4][2]에 들어가게 된다. DP 배열의 값 중..

7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 처음엔 1부터 M까지 메모리를 기준으로 비용을 구하려 했는데 시간 초과가 눈에 뻔해서 다른 방법으로 바꾸었다. 0부터 최댓값(모든 비용을 다 더한 값)까지 비용을 기준으로 배낭 채우기 방식을 이용하여 최대 메모리를 dp배열에 채워 넣는다. 최종 배열에서 가장 먼저 M이상인 값이 나온 인덱스를 출력하면 그게 바로 최소 비용이다. #include #include using namespace std; int N, M, cnt, mem[101], cost[101], dp[..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 기본적으로 DP로 길이만 저장하는 LIS를 구하는 방법에서 조금 변화를 주어 arr 배열엔 입력 값을 저장하고 len 배열엔 길이를 저장하고 dp 배열엔 현재 위치까지에서 가장 긴 수열을 가진 위치를 저장하였다. 그러고 출력할 땐 수열의 길이가 가장 길었던 위치부터 재귀 호출하여 그 수열의 처음까지 들어간 다음 출력하면서 빠져나왔다. #include using namespace st..

11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net ABCD를 계산하는 방법은 A(BCD), (AB)(CD), (ABC)D 세 가지로 나눌 수 있고 이 중에서의 최솟값이 ABCD의 값이 된다. A(BCD)에서 BCD는 B(CD), (BC)D 두 가지로 나눌 수 있고 이 중에서의 최솟값이 BCD의 값이 된다. (AB)(CD), (ABC)D도 분해하여 구한 최솟값을 저장하면 ABCD의 최솟값을 구할 수 있다. 이 과정을 표로 나타내 보면 ABCD를 구하기 위해선 A와 BCD, AB와 CD, ABC와 D를..