tony9402

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 3 위 문제는 1, 2, 3 더하기 문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다. 1234567891011121314151617181920212223242526272829#include long long dp[1000001] = {0, 1, 2, 4 }; const long long mod = 1000000009; long long DP(int n){ if (n

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 2 이 문제는 1,2,3 더하기 문제를 이용해서 풀었다. 먼저 4를 본다고 하면 DP[3] + DP[2] + DP[1]를 더한게 DP[4]의 값이다. 아래 그림을 보며 이해를 하자. 4는 3 + 1, 2 + 2, 1 + 3인 경우의 수를 알 수 있고 이를 사전 순으로 정렬하면 1 + 3, 2 + 2, 3 + 1이렇게 된다. 따라서 4를 간단한 규칙으로 정리하면 1부터 DP[4-1]까지는 1로, DP[4-1] + 1부터 DP[4-1] + DP[4-2] 까지는 2로, DP[4-1] + DP[4-2] + 1부터 DP[4-1] + DP[4-2] + DP[4-3] 까지는 3으로 채워진다. 이런 방식으로 계산을 하면 원하는 구간에서 값을 계속 vect..

알고리즘 분류 : 다이나믹 프로그래밍(DP) 문제 : 1, 2, 3 더하기 이 문제는 계산을 어떻게 할껀지 점화식을 세우면 금방 푸는 문제이다. 난 이 문제를 풀면서 재귀적인 풀이를 생각하며 풀었다. 5라는 숫자가 있을 때, 여기서 1, 2, 3을 뺀 숫자들 4, 3, 2가 1, 2, 3의 합으로 나타내는 경우의 수를 다 더하면 된다는 것을 발견하였다. 이를 수식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]이다. 여기서 n을 1, 2, 3을 빼다 보면 DP[0]인 경우가 나온다. 이럴 때, DP[0]의 값을 뭐로 하면 좋을까? 간단한 예를 보자. 2라는 숫자가 있다. 2라는 숫자는 보자마자 1 + 1와 2로 경우의 수가 나온다. 이를 내가 푼 방식으로 한번 보자. 2는 1, ..

1806번 부분합 이 문제는 투 포인터 문제로 실수 없이 코딩하면 쉽게 맞는 문제이다. 하지만 난 폰코딩을 한 문제라 실수가 좀 많았다. 알고리즘 이름대로 투 포인터(두 군데를 잡고) 쭈욱 보면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344//폰코딩#include#include using namespace std; typedef long long ll;vector vc; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll n,k,input; cin >> n >> k; for(int i=0;i>input; vc.push_back(inp..

단순 구현 문제이다. 한 문장에서 정수를 뽑고 비교연산자를 뽑아서 계산하면 된다. input data를 보면 규칙이 있다. 3 != 3을 보면 '3' + ' ' + '!' + '=' + ' ' + '3'이다. -3 > 3을 보면 '-' + '3' + ' ' + '>' + ' ' + '3'이다. 이 두 가지를 잘 보면 문장을 처음부터 읽을때 -가 나오거나 숫자가 나오면 그건 숫자라는 것을 알 수 있다. 이 숫자의 끝은 숫자가 나오다가 띄어쓰기가 나온다면 그 숫자가 끝난 부분이다. 그 다음엔 비교 연산자를 읽어야 하는데 그것은 단순히 '!', '>', ''}; int main(){ bool check = false; bool ans = false; int count = 1; int ml, mr; while ..

쉬운 문제인데 엄청난 뻘짓을 해서 계속 제출 했던 문제 그냥 모든 경우의 수를 다 돌리면 된다. 123456789101112131415161718192021222324252627#include#include using namespace std; vector vc; int sum(int n, int k, int max, int s){ int cal = s + vc[n]; int ans = (cal == k); for (int i = n + 1; i > n >> k; vc.resize(n); for (auto &i : vc)cin >> i; for (int i = 0; i

보호되어 있는 글입니다.