노는 게 제일 좋아

왜 DP 알고리즘 분류에 들어있는지 모를 문제 https://www.acmicpc.net/problem/4963 테스트 케이스가 많은 문제는 어차피 하나에 대해서 풀 수 있다면 모조리 풀 수 있고 ios::sync_with_stdio(0); cin.tie(0); 을 꼭 써주자. 이건 그냥 따로 공부할 필요도 없다. 그냥 대각선까지 가능한 BFS를 풀면된다. 탐색을 4방향에서 8방향으로 늘리면 되는 문제다. 다를게 하나도 없다. #맞은 풀이 #include #include #include #define X first #define Y second //8방향으로 이동가능 제자리 빼고 int dx[8] = {1,1,1,0,0,-1,-1,-1}; int dy[8] = {-1,0,1,-1,1,-1,0,1}; us..

전형적인 DP문제다. 처음엔 백트래킹으로 풀려했으나.. 개수가..너무 많아서 백트래킹을 어떻게 캐시로 저장할까하다가.. 방향을 틀었다. https://www.acmicpc.net/problem/11052 #처음 틀린풀이 #include using namespace std; int N; int card[1001]; int dp[1005][1005]; //카드를 살 때, 카드 수는 적되 가격은 높게 사야한다. //현재 카드가 i개 가지고 있고 카드의 수와 가격을 보면서 골라야 한다. //결국 다 뒤져봐야함 int M = -1; //최댓값 int x = 0; int func(int cnt, int val){ if(dp[cnt][x] > 0) return dp[cnt][x]; //종료조건 if(cnt > N)r..

음 아주 어렵진 않지만 생각하기 어려운 문제다. https://www.acmicpc.net/problem/12865 #맞은 풀이 #include using namespace std; //가장 가치가 크게 해야함. 가장 큰 무게가 가장 큰 가치를 보장하지 않음 //모든 것을 보고 넣을 지 말 지 정해야 함. (Brute Force지만).. 정말 다조사하면 시간초과남 //똑똑하게 조사해야함. 2^100 연산이 필요. 캐싱 필요( 값 저장) // 담을 수 있는지, 없는지 // 담을 수 있다면 담는 것이 좋은지, 아닌지 int weight[101]; // 무게 int value[101]; // 가치 int N,M; // 개수, 최대무게 int dp[102][100001]; // 값 저장 //재귀를 이용한 풀이 ..

정말 느낌대로 풀면 되는 풀이지만 검증을 해야한다 사실.. https://www.acmicpc.net/problem/1026 #맞은 풀이 #include #include #include using namespace std; int N; vector vec; vector target; int main(){ cin >> N; //A숫자 for(int i = 1; i> a; vec.push_back(a); } //B숫자 for(int i = 1; i > b; target.push_back(b); } sort(target.begin(), target.end()); // 오름차순 sort(vec.begin(), vec.end()); // 오름차순 reverse(vec.begin(),vec.end()); // 내림..

음.. 그냥 생각하고 푸는 문제다. 수학문제같다. 메모리가 192다. 128 + 64 를 의도한 건지는 모르겠다. https://www.acmicpc.net/problem/2217 #맞은 풀이 #include #include #include using namespace std; int N; int size; vector vec; int M = 0; int main(){ cin >> N; size = N; while(N--){ int a; cin >> a; vec.push_back(a); } sort(vec.begin(),vec.end()); // 오름차순 정렬 //큰 것부터 차례로 더함 for(int i = 1; i

DP의 전형적인 문제지만 DP의 과정도 출력한다고 해서.. 조금 출력을 고려해야하는 문제다. https://www.acmicpc.net/problem/12852 #처음 맞는 풀이 - 수정 전 #include using namespace std; int dp[1000001]; int num; int main(){ cin >> num; dp[1] = 0; dp[2] = 1; for(int i=3; i

이것도 DP의 예로 입력이 많고 테스트 케이스도 많아서 DP 풀어야 하는 방식과 비슷할 거라고 예상하고 들어갔다. https://www.acmicpc.net/problem/11659 #맞은 풀이 #include using namespace std; int N,M; int map[100001]; int dp[100001]; int main(){ ios :: sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i = 1; i> a; map[i] = a; dp[i] = a+dp[i-1]; } while(M--){ int a,b; cin >> a >> b; cout

이 문제도 백트래킹으로 어렵지 않은 문제다. 다만 출력 조건에 맞게끔 선택하려면 선택 과정에서 필터가 있어야 한다. https://www.acmicpc.net/problem/15657 #맞은 풀이 #include #include //N개의 수를 담을 벡터 #include //오름차순 정렬 using namespace std; int N,M; vector vec; // N개의 수를 담을 벡터 vector ans; // 수열을 넣을 벡터 void func(int cnt){ if(cnt == M){ //M개 골랐다면 출력 for(int a : ans){ cout a; vec.push_back(a); } sort(vec.begin(), vec.end()); func(0); } 여기선 필터가 이미 선택한 숫자보다..

아주아주 착각에 빠지기 쉬운 문제다. 물론 시간이 많지만 입력이 드럽게 많기 때문에 생략하고 풀어보자 https://www.acmicpc.net/problem/1654 #틀린 풀이 일부 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> K >> N; for (int i = 0; i > a; arr[i] = a; } sort(arr, arr + K); // 오름차순 standard = arr[K-1]; // 최댓값 while (1) { for (int i = K-1; i > 0; i--) { sum += (arr[i] / standard); } if (sum >= N) { cout > N >> K; f..

사실 쉬워서 안넣으려다가 26등 했길래 넣었다. https://www.acmicpc.net/problem/10816 딱 생각나는 그대로 옮겨넣었다. #include using namespace std; int N, M; int arr[20000002]; // 2천만 가량 int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i = 0; i> a; a += 10000000; arr[a] += 1; } cin >> M; for(int i = 0; i> b; b += 10000000; cout