초보개발자

입력: 일수 N, N개의 걸리는 일과 금액출력: 최대 금액알고리즘: 동적계획법, Knapsack 알고리즘소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #define plan pair #define mp(x, y) make_pair(x, y) using namespace std; vector cache; vector schedule; int benefit(int idx, int n) { if (idx >= n) return 0; int& ret = cache[idx]; if (ret != -1) return ret; ret = max(benefit(idx + 1, n), ret); if (idx + schedule[idx].first

입력: 가로 n출력: 2x1, 2x2 타일을 이용하여 2xn 타일을 나타낼 수 있는 경우의 수알고리즘: 동적 계획법, 피보나치 수열소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { int n; scanf("%d", &n); vector tile(n + 1); tile[1] = 1; tile[2] = 3; for (int i = 3; i

입력: 표현하려는 숫자 N(1≤N≤200), 양수의 개수 K(1≤K≤200)출력: 자연수 N을 K개의 양수로 표현할 수 있는 방법의 수(숫자 순서가 다르면 다른 경우)알고리즘: 동적 계획법소스코드 #define _CRT_SECRUE_NO_WARNINGS #include #include #define MOD 1000*1000*1000 using namespace std; vector cache; int sumDecomp(int n, int k) { if (n < 0 || k

입력: 동전 개수 N, 만드려는 수 K, 동전 N개의 가치출력: K를 만들 수 있는 경우의 수알고리즘: 동적 계획법소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; vector dp(10001, 0); vector coins(100); int main() { //freopen("input.txt", "r", stdin); int N, K; scanf("%d%d", &N, &K); for (int i = 0; i < N; i++) scanf("%d", &coins[i]); sort(coins.begin(), coins.begin() + N); for (int i = 0; i < N; i++) { dp[co..

입력: 집의 개수 N, 각 집을 색칠하는 데 드는 비용. 순서대로 Red, Green, Blue출력: 모든 집을 색칠하는데 드는 최소비용조건: 이웃한 집은 서로 색이 같을 수 없다.알고리즘: 동적계획법소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; #define min(a, b) (a < b ? a : b) #define MAX 987654321 vector dp; vector house; int n; int coloring(int, int); int main() { scanf("%d", &n); house = vector(n, vector(3)); dp = vector(n, vector(3, -1)); for (in..