다이나믹 프로그래밍 문제입니다. 팰린드롬 = 뒤집어도 같은 문자 ex) 121, 1234321, 919, 111, 22, 3 숫자가 주어지고 범위가 주어졌을 때 팰린드롬인지 아닌지 출력하는 문제입니다. 모든 범위에 대한 팰린드롬의 결과를 미리 구합니다. DP[x][y]는 x에서 y까지의 범위가 팰린드롬인지를 가지고 있습니다. 먼저 범위의 길이가 1과, 2에 대해서는 미리 구해줍니다. for (int i = 1; i n; memset(arr, 0, sizeof(arr)); memset(DP, 0, sizeof(DP)); for (int i = 1; i
다이나믹 프로그래밍 문제입니다. n의 숫자가 주어졌을 때 가능한 경우가 몇개인지 찾는 문제입니다. A = 1 B = 2 C = 3 .... Y = 24 X = 25 Z = 26 으로 하였을 때 25의 경우 1. BE 2. X 처럼 두가지 경우가 가능합니다. 한자리수가 1~9일 때 DP[c] = DP[c - 1]; 두자리수가 10~26일 때 DP[c] = DP[c - 2] + DP[c]; 계산이 불가능 할 때 if (stoi(n.substr(0, 1)) == 0) { cout n; if (stoi(n.substr(0, 1)) == 0) { cout
다이나믹 프로그래밍 문제입니다. 피보나치 수열의 규칙을 하고 있어서 DP[i] = DP[i - 1] + DP[i - 2]; 로 점화식을 세워서 문제를 풀었습니다. #include #include #include #include using namespace std; int DP[1000010]; int main(int argc, char *argv[]) { int n; memset(DP, 0, sizeof(DP)); DP[1] = 1; DP[2] = 2; cin >> n; for (int i = 3; i
다이나믹 프로그래밍 문제입니다. 2차원 배열을 이용해서 같은 문자를 체크하고 같은 문자일 경우 숫자를 1씩 추가해서 길이를 구하였습니다. 그리고 같은 문자일 경우 문자를 배열에 저장해서 마지막에 저장된 문자값을 출력하여 문제를 풀었습니다. #include #include #include using namespace std; int map[1010][1010]; string stringMap[1010][1010]; int moveX[3] = { 0, -1, -1 }; int moveY[3] = { -1, 0, -1 }; int main(int argc, char *argv[]) { int maxNum = 0; string s1; string s2; string s3; cin >> s1; cin >> s2;..
다이나믹 프로그래밍 문제입니다. 인접한 파일을 합쳐서 하나의 파일을 만들 때 최소 비용을 구하는 문제입니다. for (int i = 2; i 0; --j){ DP[j][i] = 987654321; for (int k = j; k > testcase; while (testcase--) { memset(DP, 0, sizeof(DP)); memset(arr, 0, sizeof(arr)); int n; cin >> n; for (int i = 1; i > arr[i]; sum[i] = sum[i - 1] + arr[i]; } for (int i = 2; i 0; --j) { DP[j][i] = 987654321; for (int k = j; k
다이나믹 프로그래밍 문제입니다. N줄에 숫자가 3개씩 적혀있는데 아래로 내려가거나, 바로 아래와 인접해 잇는곳으로만 내려갈 수 있습니다. 이 때 얻을 수 있는 가장 큰 점수와 작은 점수를 구하는 문제입니다. 각각의 위치에서 현재 값과 내려가면서 선택할 수 있는 가장 큰 값을 maxDP에 저장합니다. n의 줄까지 이를 반복하여 각위치의 최대값들을 비교해서 가장 큰값을 출력합니다. #include #include using namespace std; int map[100010][3]; int minDP[3]; int maxDP[3]; void init() { for (int i = 0; i < 100010; ++i) { for (int j = 0; j < 3; ++j) { map[i][j] = 0; } } ..