알고리즘/다이나믹 프로그래밍 썸네일형 리스트형 [B15990] - 1,2,3 더하기 5 https://www.acmicpc.net/problem/15990 마지막항이 무엇인지 고려하여 점화식을 세우면 된다. 12345678910111213141516171819#includeusing namespace std;long long d[100001][4];int main() { int T; cin >> T; d[1][1] = d[2][2] = d[3][3] = 1; d[3][1] = d[3][2] = 1; for (int i = 4; i > n; cout 더보기 [B1463] - 1로 만들기 https://www.acmicpc.net/problem/1463주어진 조건에 따라 점화식을 세우면 된다. 123456789101112131415161718192021222324#include using namespace std;int main(){ int n; cin >> n; int d[n + 1] = { 0, }; for (int i = 0; i = 1; i--) { if (i % 3 == 0) { if (d[i / 3] > d[i] + 1) d[i / 3] = d[i] + 1; } if (i % 2 == 0) { if (d[i / 2] > d[i] + 1) d[i / 2] = d[i] + 1; } if (d[i - 1] > d[i] + 1) d[i - 1] = d[i] + 1; } cout 더보기 [B1520] - 내리막길 https://www.acmicpc.net/problem/1520 dfs에 메모이제이션을 통해 연산량을 줄여서 풀면 시간초과가 안납니다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std;int a[501][501];int d[501][501];int dx[] = { 0,0,1,-1 };int dy[] = { -1,1,0,0 };int m, n;int ans = 0;int dfs(int xnode, int ynode){ if (xnode == m - 1 && ynode == n - 1) { return 1; } if (d[xnode][ynode]!=-1) return d.. 더보기 [B9465] - 스티커 https://www.acmicpc.net/problem/9465 스티커입니다. 스티커를 최대한의 점수를 갖게 떼어내는 방법을 구하는 것이 목표입니다.최종답을 구할 때 이전 상태를 이용해야하기 때문에 dp로 풀 수 있습니다.어떤 위쪽 칸에 들어가는 최대값을 구하고 싶다면 그 전전칸의 위쪽의 최대값+전 칸의 아래쪽 값과 그 전 칸의 아래쪽 값 중 큰 값에 a[i][0]을 더해주면 됩니다.d[i][0]=max(d[i-2][0]+a[i-1][1],d[i][1])+a[i][0]으로 표현할 수 있네요그런데 이 값보다 전칸의 위쪽값이 더 크다면 어떨까요?즉 a[i][0]의 스티커를 떼어내지 않는 경우도 있을 수 있습니다.그러므로 d[i][0]=max(d[i-1][0],max(d[i-2][0]+a[i-1][1],d[.. 더보기 이전 1 다음