너와 나의 스토리

문제: https://www.acmicpc.net/problem/5557 문제 풀이: 주목할 조건 1. 중간 연산 결과가 [0, 20] 사이의 값이어야 한다. 2. 각 값은 [0, 9] 사이의 값이다. 3. 올바른 등식의 개수는 $2^63-1$ 이하이다. -> long long 사용해야 한다. dp[index][현재까지의 값]=경우의 수 로 dp를 만들고, 2중 포문으로 문제를 풀 수 있다. 소스 코드: 더보기 #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n,arr[102]; ll dp[102][21]; i..

문제: https://www.acmicpc.net/problem/9095 문제 풀이: n=3인 경우 3 = 1+1+1 = 1+2 = 2+1 = 3 이렇게 4가지 경우가 있다. n=4인 경우 4 = 3+1 -> [n=3]인 경우에 1씩 다 더하면 된다. = 2+2 -> [n=2]인 경우에 2씩 다 더하면 된다. = 1+3 -> [n=1]인 경우에 3씩 다 더하면 된다. 그럼 총 7가지 경우의 수가 나온다. 즉, dp[n]=dp[n-1]+dp[n-2]+dp[n-3] 으로 점화식을 세울 수 있다. 소스 코드: 더보기 #include #include #include #include #include #include #include using namespace std; int dp[13],n,tc; int main..

문제: https://www.acmicpc.net/problem/2225 문제 풀이: 예제를 통해 규칙성을 찾아보자 위 예제를 통해 점화식이 다음과 같이 세울 수 있다 * dp[k][n]: 정수 k개를 사용해서 n을 만든 경우 수 점화식 → dp[k][n]= dp[k-1][0]+dp[k-1][1]+ ... +dp[k-1][n] = $\sum_{i=0}^{n}dp[k-1][i]$ #include #include #include using namespace std; typedef long long ll; ll n, k, dp[202][202]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> k; for ..

문제: https://www.acmicpc.net/problem/2579 문제 풀이: 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. => K번째 계단을 밟을 수 있는 경우는 다음과 같다: 1. stairs[K-3], stairs[K-1] -> stairs[K] 2. stairs[K-2] -> stairs[K] 위 그림과 같이 항상 조건을 만족하게 된다. 소스 코드: 더보기 #include #include using namespace std; int n,arr[305],dp[305]; int main() { ios::sync..

문제: https://www.acmicpc.net/problem/14863 문제 풀이: dp[현재 도시][현재까지 걸린 시간] = dp[이전 도시][이전 도시까지 걸린시간]+모금액 진전 도시까지 도달하는데 걸린 시간들을 기준으로 다음 도시까지 걸리는 시간과 모금액을 쌓아가며 저장한다. 소스 코드: int n,k; int dp[100][100001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> k; for (int i = 0; i > q >> w >> e >> r; if (i == 0) { dp[0][q] = w; dp[0][e] = max(..

문제: https://www.acmicpc.net/problem/14697 소스 코드: int n,arr[3]; bool dp[301]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); for (int i = 0; i > arr[i]; cin >> n; dp[n] = true; for (int i = n; i > 0; i--) { if (!dp[i]) continue; for (int j = 0; j = 0) dp[i - arr[j]] = true; } } if (dp[0]) cout

문제: https://www.acmicpc.net/problem/1890 문제풀이: "경로의 개수는 2^63-1보다 작거나 같다." -> long long "메모리 제한: 128 MB" -> DP 이미 갔던 길 다시 안가고 그 지점에서 갈 수 있는 경우의 수+1 해주면 됨 * 함수 리턴 타입 확인 잘하자.... int func()해서 계속 틀림 ㅠㅅㅠ 소스코드: int n, arr[100][100]; long long dp[100][100]; long long func(int x, int y) { if (x == n - 1 && y == n - 1) return 1; if (x >= n || y >= n) return 0; long long& ret = dp[x][y]; if (ret != -1) ret..

문제: https://www.acmicpc.net/problem/11722 문제 풀이: https://hororolol.tistory.com/103 (BOJ) 11053 가장 긴 증가하는 부분수열 문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio.. hororolol.tistory.com ㄴ 거의 같은 문제 부등호 방향만 바꾸면 됨 소스코드: 풀이1 - 시간 복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios:..