Dynamic Programming3 [BOJ] 1912번: 연속합 1912: 연속합풀이dp[i] = max(dp[i - 1] + A[i], A[i])이다. (A[i]는 i번째 숫자이다.) 참고: i는 1부터 시작.점화식이 이렇게 나오는 이유는 문제가 "연속적"이라는데 중점을 두고 있기 때문이다. 코드sync_with_stdio(false)를 적용하면 scanf, printf보다 더 빠르다. 8ms, 12ms 12345678910111213141516171819202122232425#include using namespace std;const int mx = 100000 + 1;int n, A[mx], DP[mx]; inline int max(int a, int b) { return a > b ? a : b;}int main(){ cin.sync_with_stdio(fa.. 2018. 3. 28. [BOJ] 1003번: 피보나치 함수 1003번: 피보나치 함수풀이그래프를 그려보면 0과 1이 호출될 때 일정한 규칙이 나오는 것을 알 수 있다. 그래서 dp[i][0]은 i번째 수에서 0의 호출 횟수이고 dp[i][1]은 i번째 수에서 1의 호출 횟수이다.또는 N이 주어질 때 dp[N]은 0의 호출 횟수이고 dp[N+1]은 1의 호출 횟수가 되는데 이 이유는 잘 모르겠다... (아시는 분은 알려주시면 정말 감사드리겠습니다!)코드1번째12345678910111213#include int main(){ int n, k; scanf("%d", &n); for (int j = 0; j 2018. 3. 25. [BOJ] 11726번: 2xn 타일링(feat. DP) 11726: 2xn 타일링풀이Dynamic Programming으로 풀 수 있는 문제다. dp[i] = dp[i - 1] + dp[i - 2]코드123456789#include int main(){ int n, i, dp[1001] = { 1, 1 }; scanf("%d", &n); for (i = 2; i 2018. 3. 25. 이전 1 다음