문제링크 : https://www.acmicpc.net/problem/17265 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, minV = MAX, maxV = -MAX;int dx[] ={1, 0}, dy[] = {0, 1};char arr[5][5];void dfs(int y, int x, int n){ if(y==N-1 && x==N-1) { minV = min(minV, n); //최솟값, 최댓값 갱신 maxV = max(maxV, n); return; } for(int i=0; i= N || nx >= N) c..
문제링크 : https://www.acmicpc.net/problem/17213 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;ll N, M;ll dp[31][31];void func(){ dp[0][0]=1; //첫 번째 값 1 for(int i=1; i> N >> M; func(); cout 중복 조합 문제이다.간단하게 생각해보면 nHm 이지만, 모든 종류의 과일이 적어도 1개씩 있어야 한다는 조건 때문에 nHm-n이 된다.이를 조합으로 변환하여 계산을 해주면 된다.그러면 nCr = n+r-1Cr = n+m-n+1Cm-n이 된다.해당 계산은 파스칼 삼각형 공식을 ..
문제링크 : https://www.acmicpc.net/problem/4097 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int arr[250001];int dp[250001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); while(true) { int result = -MAX; cin >> N; if(N==0) break; for(int i=0; i> arr[i]; dp[0] = arr[0]; for(int i=1; i 구간이 비어..
문제링크 : https://www.acmicpc.net/problem/16500 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;string s;int N;string arr[101];int dp[101];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> s >> N; for(int i=0; i> arr[i]; dp[s.size()]=1; for(int i=s.size(); i>=0; i--) { for(int j=0; j 어떻게 dp 식을 세워야 하는지 감이 잘 안 잡혔던 문제이다.다른..
문제링크 : https://www.acmicpc.net/problem/1660 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int arr[121], dp[300001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); for(int i=1; i> N; for(int i=1; i 먼저 사면체 대포알 수 구하는 공식을 이용하여 미리 사면체 대포알 갯수를 구해준다.이때 문제의 대포알 최대 갯수가 30만인데, 이에 맞게 가능한 최대 i 값인 120까지 구하도록 하였다. 이후 dp 배열을 초기화 해주는데 사면체를 생각하지 ..
문제링크 : https://www.acmicpc.net/problem/1793dp = [0 for i in range(251)]while(True): try: n = int(input()) dp[0]=1 dp[1]=1 dp[2]=3 dp[3]=5 for i in range(4, n+1): dp[i] = dp[i-1] + 2*dp[i-2] print(dp[n]) except: break 출력 범위로 인해 python으로 푼 문제이다.C++로 풀 경우 큰 수를 다뤄야 하기 때문에 훨씬 복잡해진다. 점화식의 경우 N=3 까지 그림을 직접 그려보면 어렵지 않게 알 수 있다.N=3의..
문제링크 : https://www.acmicpc.net/problem/12852 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int dp[1000001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=1; i 기본적인 초기화는 3번 조건에 해당하는 값으로 설정해준다.이에 따라 각 idx에 해당 하는 값은 idx-1의 횟수를 필요로 하므로 이에 맞게 초기화를 진행했다. 이후 1, 2번 조건에 대해 체크하며 더 작은 경우를 확인해준다.또 이어서 기존 3번 조건과 1, 2번 조건을..
문제 링크 : https://www.acmicpc.net/problem/2502 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int D, K;int A[31];int B[31];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> D >> K; A[0] = 1; A[1] = 0; //A, B B[0] = 0; B[1] = 1; for(int i=2; i 먼저 간단하게 규칙을 찾아보면 다음과 같다.i = 0A (= A*1 + B*0)i = 1B (= B*0 + B*1)i = 2A + Bi = 3A + ..
문제 링크 : https://www.acmicpc.net/problem/1263 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, a, b;vectorv;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> a >> b; v.push_back({b, a}); } sort(v.begin(), v.end(), greater()); //일을 끝내야 하는 시간이 큰 값부터 정렬 int cur = v[0].first - v[0].second; //현..
문제링크 : https://www.acmicpc.net/problem/3151 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int arr[10001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> arr[i]; sort(arr, arr+N); ll result = 0; for(int i=0; i 3가지 합이 0이 되는 경우를 찾아야 한다.이를 위해 2가지 값을 고정 (2가지 값의 합) 시켜 놓고 나머지 1개의 값을 이분 탐색을 통해 찾아준다...
문제링크 : https://www.acmicpc.net/problem/2141#include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;ll sum = 0;vectorv;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> a >> b; v.push_back({a, b}); sum+=b; } sort(v.begin(), v.end()); ll tmp = 0; for(int i=0; i= (sum+1)/2) //정렬된 상태의 중앙값 출력 ..
문제링크 : https://www.acmicpc.net/problem/19598 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, B, C; //강의 갯수, 시작 시간, 종료 시간int cnt=1; //최소 강의실vectorv;priority_queue, greater> pq;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> B >> C; v.push_back({B, C}); } sort(v.begin(), v.end()); for(int i=..
문제링크 : https://www.acmicpc.net/problem/1374 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, A, B, C; //강의 갯수, 강의 번호, 시작 시간, 종료 시간int cnt=1; //최소 강의실vectorv;priority_queue, greater> pq;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> A >> B >> C; v.push_back({B, C}); } sort(v.begin(), v.end());..
문제링크 : https://www.acmicpc.net/problem/5545 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, A, B, C; //토핑 갯수, 도우 가격, 토핑 가격, 도우 열량int arr[10001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> A >> B >> C; for(int i=0; i> arr[i]; } sort(arr, arr+N, greater()); //토핑 열량이 높은 순서대로 비교 int result = C/A; //1원당 열량 (최고)..
문제링크 : https://www.acmicpc.net/problem/20044 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int arr[10001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> arr[i]; } sort(arr, arr+2*N); //정렬 int score = MAX; for(int i=0; i 2*N 만큼 입력받고, 입력받은 값을 정렬시켜준다.이후 인덱스를 옮겨가며 배열의 양 끝값을 더해주고 이중 제일 작은..