Approach 이 문제를 완전탐색으로 접근해보면, 앞에서부터 모든 문자열에 대해서 되는지를 체크해주면 된다. 다만, 비둘기집의 원리에 의해서 중복되는 계산이 매우 많다는 사실을 캐치할 수 있다. 이 지점에서 Memoization을 활용한 DP를 활용해서 중복되는 계산을 줄일 수 있음을 생각할 수 있다. dp[i] : s의 i 번쨰 index까지는 매핑되었고, 그 이후의 문자열을 매칭지을 수 있는지 여부 (가능하면 1, 아니면 0) dp[i] = max(dp[i + v[j].size()]) for all j s.t s.substr(i, i + v[j].size()) == v[j] (v[j] 는 j번째 문자열) Code #include #define fastio ios_base::sync_with_stdi..

Approach 완전 탐색 기법으로 해당 문제를 푸는 식으로 문제를 접근해보면, 길이가 N - 1인 계단수의 정보를 활용해서 길이가 N인 계단수를 구할 수 있다는 점을 쉽게 파악할 수 있다. 다만, 마지막 수가 1 ~ 8인지 0이나 9인지 여부에 따라서 경향성이 달라지므로 끝나는 숫자에 대한 정보가 필요한데 이를 dp에 저장해두면 쉽게 풀 수 있다. Let dp[i][j] : 마지막 수가 j이면서 길이가 i인 계단 수 (dp[1][0] = 0, dp[1][1 ~9] = 1 : Initial value) dp[i][j] : dp[i - 1][j - 1] + dp[i - 1][j + 1] for j $\in$ {2, 3, 4, 5, 6, 7, 8, 9} dp[i]j] : dp[i - 1][j + 1] for..

Approach 전형적인 냅색 문제에서 표현만 달라진 형태이지, 완벽히 접근방법이 동일하다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[100][10001]; int n, k; vector coin; int memoi(int x, int k){ if(x == n) return (k == 0 ? 0 : 987654321); if(k < 0) return 987654321; int& ret = dp[x][k]; if(ret != -1) return ret; int value = coin[x]; return ret = min(memoi(x + 1, k), ..

Approach path(y, x) : (y, x)ㄱ에서 시작해서 맨 아래줄까지 재려가는 부분 경로의 최대합 이렇게 정의했을 경우, path(y, x)는 y ~ n - 1까지의 아직 해결하지 못한 조각들에 대한 값을 정의하는 부분이므로 이전 입력값에 영향을 받지 않는다. 즉, (y, x)까지 어떤 경로로 도착했건 남은 부분 문제는 항상 최적으로 풀어도 상관이 없다. 이러한 성질을 최적 부분 구조(Optimal substructure)이라고 한다. 이러한 성질 때문에 지금까지의 선택과 관계 없이 각 부분 문제를 최적으로 풀기만 하면 전체 문제의 최적해도 알 수 있게 되는 것이다. 따라서 탑-다운 방식으로 이 문제를 해결할 수 있게 된다. Code #include #define fastio ios_base:..

Approach *에 몇 글자가 대응하는지 여부가 가장 중요하다. 이 문제를 완전탐색을 통해서 해결할 수 있다. 완전탐색을 통해 해결할 수 있으나, 문자열의 길이가 100자리 이하라는 것을 감안할 때 비둘기집 원리를 이용하면 총 101 * 101 가지 이하만 계산해주면 된다는 것을 이해할 수 있다. (즉, 중복되는 계산이 무조건적으로 생기므로 메모이제이션을 활용하면 중복되는 계산을 줄일 수 있다.) Code 1. $0(N^3)$로 푸는 풀이 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; string W; string T; int dp[101][101]; int memoizat..

Approach https://viyoung.tistory.com/307 문제와 근본적으로 비슷한 측면이 많다. [백준 8394번] [동적 계획법] 약수 Approach 잘 생각해보면, 해당 사람이 악수를 할 수 있는지 여부는 앞의 사람이 악수를 했는지 여부와 관련이 있다 dp[i][0] : i번째 사람까지 참석했다고 했을 때의 경우의 수 중 i번째 사람이 앞 사 viyoung.tistory.com 1이 나올 수 있는지 여부는, 이전의 숫자가 1인지 아닌지 여부와 관련이 있다. (고등학교때 배운 수형도와 비슷한 측면으로 이해해주면 충분하다) dp[i][0] : i번째 자리까지 고려했을 때 나올 수 있는 총 경우의 수 중, i번째 자리가 1이 아닌 경우 dp[i][0] : i번째 자리까지 고려했을 때 나올..

Approach 잘 생각해보면, 해당 사람이 악수를 할 수 있는지 여부는 앞의 사람이 악수를 했는지 여부와 관련이 있다 dp[i][0] : i번째 사람까지 참석했다고 했을 때의 경우의 수 중 i번째 사람이 앞 사람과 악수를 하지 않는 경우 dp[i][1] : i번째 사람까지 참석했다고 했을 때의 경우의 수 중 i번째 사람이 앞 사람과 악수를 하는 경우 dp[i][0] = dp[i - 1][0] + dp[i - 1][1] (악수를 하지 않으므로, 앞에 있는 사람이 악수를 했는지 안했는지 여부가 중요하지 않음) dp[i][1] = dp[i - 1][0] (앞 사람과 악수를 해야하므로, 앞에 있는 사람이 무조건 악수를 하면 안된다.) Code #include #define fastio ios_base::syn..

Approach 잘 생각해보면, 연속된 수들의 곱을 결정짓기 위해서는 이전 결과값이 사용된다는 느낌을 받을 수 있다. 이 지점에서 DP를 활용할 수 있곘다는 느낌을 받으면 쉽게 풀 수 있다. Let dp[i] : i번째 숫자로 끝나면서 연속된 수들의 곱이 최대가 되는 값 dp[i] = max(dp[i - 1] * v[i], v[i]) (단, v[i]는 i번째 수) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; double dp[10001]; int n; cin >> n; double f; cin >> f; dp[0] = f;..