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;..

Approach Naive하게 생각해보면, 이 문제를 풀기 위해서는 주어지는 input에서 trash bin이 어디 있는지를 파악해야 한다. 그리고, 해당 trash bin을 기준으로 거리를 판단해주면 된다. 예를 들어 trash bin이 놓인 index가 1, 5라고 하면, 그 사이에 놓인 2,3,4는 가장 가까운 trash bin을 찾아나가게 되는데 이는 해당 trash bin 사이의 distance에 의해서 지배받게 된다. 만약 두 trash bin 사이의 거리가 짝수인 경우에는 2로 나누었을 때의 몫까지의 시그마 합의 2배이고, 홀수인 경우에는 거기에 몫을 한번 빼주면 된다. Let trash bin's position is $x_i$ and $x_j$. (s.p.s $x_i < x_j$). De..

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..