Approach 투자금은 이전 시점의 금액에 의해서 지배받는다는 것을 캐치했으면, 점화식 관계를 이루고 있다는 것을 쉽게 파악할 수 있다. dp[i] : i년 투자했을 때 총 자산 dp[i] = max{dp[i - 1] * 1.05, dp[i - 3] * 1.2, dp[i - 5] * 1.35} Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; long long dp[11]; memset(dp, 0, sizeof(dp)); int h, y; cin >> h >> y; dp[0] = h; dp[1] = h * 1.05; dp[2]..

Approach 파스칼 삼각형 구하고, 원하는 범위의 값을 다 더해주면 된다. Let define dp[n][r] : nCr value. Therefore dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] Approach #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[32][32]; int main(void) { fastio; memset(dp, 0, sizeof(dp)); dp[1][1] = 1; for (int i = 2; i r >> c >> w; long long count = 0; int index = 0; for (int i ..

Approach 이 문제를 보고 그리디 문제라고 오해하기 쉬우나, 2원과 5원의 최대공약수가 1이므로 단순히 큰 숫자를 더 많이 가져가는 식의 접근 방법이 통하지 않는다. dp[i] : minimum number of constructing i(Won) using 2 and 5 Therefore dp[i] = min(dp[i - 2], dp[i - 5]) + 1 (Base case : dp[2] = 1, dp[5] = 1) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[100001]; int main(void){ fastio; memset(dp, -1, ..

Approach https://viyoung.tistory.com/292 와 완전히 유사하다. [백준 15312번] [동적 계획법] 이름 궁합 Approach 한 글자가 숫자에 하다씩 매핑되는 양상이므로 replace 등의 함수를 활용하는 것이 아니라, ASCII를 활용하여 대문자와 주어진 숫자를 하나씩 매핑해주는 방식을 사용해주면 된다. 추가적으 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; string a, b; cin >> a >> b; queue q; for(int i = 0; i ..

Approach 주어진 문장인 "welcome to code jam"의 순서를 지키면서 몇 개 만들 수 있는지가 목표이므로, 각 알파벳이 등장할 때 주어진 문장에서 어느 부분까지를 활용할 수 있는지를 체크해주면 된다. Let define dp[i] : 주어진 i번째 index까지를 만들 수 있는 subsentence의 수 Suppose that input value is x, dp[k] += dp[k - 1] for every k s.t x == dp[k]. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[19]; int main(void){ fastio;..

Approach 한 점을 기준으로 가능한 경우는 2가지 밖에 없다. 현재 방향으로 이동 현재 방향에서 오른쪽으로 이동 잘 생각해보면, 전자의 경우는 행이 주는 경우이고 후자의 경우는 열이 주는 경우이다. 그리고 바라보는 방향은 크게 중요하지는 않은데 왜냐하면 대칭이기 때문이다. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (if i or j == 1, dp[i][j] = 1) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int t; cin >> t; long long dp[26][26]; memse..

Approach Consonant와 vowel 사이의 관계식이 주어진 상황이므로 DP를 활용하여 풀 수 있음을 직감적으로 느끼면 된다. DP 식 자체는 다음과 같다. dp[i + 1][0] = dp[i][1] * c dp[i + 1][1] = (dp[i][0] + dp[i][1]) * v (0은 consonant, 1은 vowel) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; long long dp[16][2]; // regard of x + 0 : consonant, 1 : vowel int c, v, l; int main(void){ //자음 뒤 무조건 모음 i..

Approach https://viyoung.tistory.com/295 문제와 완벽히 동일하다. [백준 9655번] [동적 계획법] 돌 게임 Approach 최선의 선택을 한다는 사실을 잘 생각해보면, 결과적으로 최소한의 움직임만 고려해주면 된다. 가장 최소한의 움직임에서 움직임이 늘어나는 경우는 3이 선택되어야하는 상황에 1을 선택 viyoung.tistory.com 다만, 마지막에 돌을 둔 사람이 지는 것이므로 승자만 바꿔주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[1001]; int n; int dp_value(int x) { if ..