너와 나의 스토리

문제링크: https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum/description/입력: 정수 리스트출력: sub-array의 합이 음수인 것의 개수  풀이 방법현재 합이 짝수일 때, 홀수를 더해야 홀수가 되고현재 합이 홀수일 때는 짝수를 더해야 홀수가 된다.예: [1, 3, 5]짝수가 처음부터 한 개인 이유 -> 0으로 시작하기 때문 0135지금까지 숫자 합0149짝수 개수1122홀수 개수0123count sum01(짝수 개수를 더함)2(홀수 개수를 더함)4(짝수 개수를 더함)결과   4 코드class Solution(object): def numOfSubarrays(self, arr): MOD = 10**9 + 7 ..

문제링크: https://leetcode.com/problems/largest-divisible-subset/description/?envType=daily-question&envId=2024-07-06입력: distinct 양의 정수 리스트조건: 리스트에 들어 있는 모든 정수 쌍(pair)이 나누어 떨어져야 한다.  -> a % b == 0 이거나 b % a ==0 둘 중 하나의 조건만 만족하면 됨.출력: 위 조건을 만족하는 가장 큰 사이즈의 리스트 풀이 방법일단 정렬예: 입력이 [1, 3, 5, 6, 8, 10, 12]라고 하자각 값에 대해서 를 저장해 보자. index는 0부터 시작nums[i] % nums [j] == 0이면 count++하면 된다.이중 포문으로 처리한다고 했을 때, 자기 자신과 ..

문제: 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