hades

🥅 문제https://www.acmicpc.net/problem/1562 🔍 설계0~9까지의 모든 수를 포함하는 계단 수가 몇 개인지 구해야 한다. 길이가 n인 것이 n+1인 계단 수를 이루는 데 사용될 수 있으므로, 다이나믹 프로그래밍을 이용한다. 사용한 숫자를 기록하기 위해 비트마스킹을 이용한다. 9만 사용되었다면, 이진수로 1000000000인 512에 저장하는 방식이다. dp[사용한 숫자][길이][마지막 숫자]로 구상한다. 다이나믹 프로그래밍이므로, 초깃값을 설정해야 하는데, 길이가 1이라면, 계단 수의 개수는 그 수만 해당되므로 1로 설정한다. 길이가 2 이상일 때, 0으로 끝난다면 마지막 수가 1만 되고, 9로 끝난다면 마지막 수가 8만 되고, 그 사이라면 마지막 수는 ± 1이 된다. 새로..

🥅 문제https://www.acmicpc.net/problem/1509 🔍 설계부분 문자열들 중에서 어디서부터 어디까지 팰린드롬인지 먼저 구해야 한다. 팰린드롬을 구하는 방법은 다음과 같다. 문자 개수가 하나인 경우, 팰린드롬이다.문자 개수가 2개인 경우, 두 문자가 같으면 팰린드롬이다.문자 개수가 3개 이상인 경우, 맨 앞과 맨 뒤가 같고, 가운데가 팰린드롬이면, 팰린드롬이다. 이제 팰린드롬을 구했으니, 최소로 분할해야 한다. 최소 분할 수는 반복문으로 어떤 인덱스까지의 최소 분할 개수를 저장하면서, 구할 수 있다. 주의해야할 점은 팰린드롬이 기본적으로 성립해야 한다는 것이다. 기존에 저장된 값과 0부터 end 사이의 인덱스를 start라고 할 때, start부터 end까지 팰린드롬이 성립한다면,..

🥅 문제https://www.acmicpc.net/problem/15486 🔍 설계데이터가 엄청 많고, 최대의 이익을 얻도록 상담을 구성하므로, 다이나믹 프로그래밍으로 방향을 잡았다. dp[i]에는 상담을 i번째 날까지 했을 때, 최대 이익을 저장한다. i로부터 상담이 끝나는 날은 i + 소요 날 - 1이고, 이것을 finish_day로 지정하였다. i번째 날에 상담을 시작한다면, 상담이 끝난 날 얻는 이득인 dp[finish_day]는 dp[i-1] + 상담 이익이다. 여기서 dp[i]가 아닌 dp[i-1]을 더해야 함에 유의한다. dp[i]는 i번째 날까지 상담이 이루어지므로 상담을 시작할 수 없다. 또한, i번째 날에 상담이 끝나지 않는 경우를 고려하면, 전날까지의 이익과 비교하여 최댓값을 구하..

🥅 문제https://www.acmicpc.net/problem/9251 🔍 설계초기에는 일차원 배열을 선언하고, strA와 strB를 이중 반복문으로 순회하면서, 같으면 그 인덱스까지의 최장 거리를 증가시키는 방식으로 시도했지만, 순서가 고려되지 않는 문제가 발생한다. 따라서, 이차원 배열로 선언하여, dp[i][j]는 strA에서 i번째, strB에서 j번째까지 최장 길이를 저장한다. dp[0][0]을 초깃값으로 이용하기 위해, 반복문을 1부터 문자열의 길이까지 반복한다. 문자열은 0부터 시작하므로, 문자열에서는 i-1, j-1을 이용한다. strA[i-1]과 strB[j-1]이 같으면, dp[i][j]를 dp[i-1][j-1]+1로 갱신한다. 두 문자열에서 각각 i와 j가 되기 전의 최장 길이에..

🥅 문제https://www.acmicpc.net/problem/1932 🔍 설계어떤 수까지의 경로 상의 합은 맨 위부터 왼쪽 아래, 오른쪽 아래를 계속 선택하여 얻어지므로 다이나믹 프로그래밍을 이용한다. 일차원 배열에 수를 모두 담았을 때, 어떤 수가 n번째 줄에 있다면, 왼쪽 아래에 있는 수는 +n에 있고, 오른쪽 아래에 있는 수는 +(n+1)에 있다. 👊 풀이#include #include #include #include using namespace std;int n, number, k, result;vector triangle(1, -1);vector dp(500 * 501 / 2);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nul..

🥅 문제https://www.acmicpc.net/problem/2096 🔍 설계전 줄까지의 결과에 새로운 줄에 입력받은 수를 더하여 최대 최소를 구하는 다이나믹 프로그래밍 문제이다. 처음 메모리 제한을 보지 않고, 100000줄을 다 받았는데, 메모리 초과가 발생하였다. 새로운 줄에 입력받을 수와 전 줄까지의 점수, 새로운 줄까지의 점수만 필요하므로 벡터를 3개만 생성한다. 다이나믹 프로그래밍에서는 초기화가 항상 중요한데, 첫째 줄까지의 점수는 입력받은 수 그대로이다.  👊 풀이#include #include #include using namespace std;int n, col;int dy[] = { -1,0,1 };vector new_line(3);vector> before_score(3, {..

🥅 문제https://www.acmicpc.net/problem/1149 🔍 설계바로 이전 집에서의 색과 다른 색을 칠하기 위해 각 집을 고려할 때마다 큐에서 하나씩 꺼내서 칠할 색을 결정한다. 큐에는 이전 집에서의 색과 비용이 저장되어 있다. 하지만, 칠할 수 있는 색에 대하여 모든 경우를 고려할 경우, 메모리 초과가 발생한다. 따라서, 어떤 집까지 색을 칠했을 때, 최소 비용을 갱신하고, 그 때의 색과 비용을 큐에 저장하면 메모리 초과 문제를 해결할 수 있다. 큐를 이용하지 않고, 간단하게 다이나믹 프로그래밍으로 해결할 수도 있다. 아이디어는 같다. 👊 풀이1#include #include #include #include using namespace std;int n, result = 1e9 +..

🥅 문제https://www.acmicpc.net/problem/17626 🔍 설계  모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로, 그 자연수를 이루는 제곱수들의 수는 다이나믹 프로그래밍을 이용하여 구할 수 있다. 예를 들어, 61 = 5^2 + 6^2이므로 5^2의 최소 제곱수 개수인 1과 6^2의 최소 제곱수 개수인 1을 더해 제곱수 2개를 이용하여 구할 수 있다.  👊 풀이#include #include #include #include using namespace std;int n;vector dp(50001, 1e9 + 7);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; ..

🥅 문제https://www.acmicpc.net/problem/11726 🔍 설계직접 그려서 파악해보면, 파란색 화살표는 2*1 타일을 추가하여 만들어지고, 빨간색 화살표는 1*2 타일을 두 개 붙인 것을 추가하여 만들어진다. 즉, dp[i] = dp[i-1] + dp[i-2]라는 것을 알 수 있다. 👊 풀이#include #include #include #include using namespace std;int n;vector dp(1001);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; dp[1] = 1; dp[2] = 2; for (int i = 3; i

🥅 문제https://www.acmicpc.net/problem/9095 🔍 설계1 = 12 = 1 + 1 = 23 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 34 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 3 + 1 = 1 + 1 + 2 = 2 + 2 = 1 + 3으로 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]이라는 것을 알 수 있다. dp[0]을 0으로 초기화하면, 1부터 반복문을 시작할 수 있다. 단, 범위를 주의해야 한다. 👊 풀이#include #include using namespace std;int t, n;vector dp(11);int main(void){ dp[0] = 1; for (int i = 1; i = 0) { ..