노는 게 제일 좋아

1초지만 은근히 숫자가 적어서 해볼만하다 생각한 문제 https://www.acmicpc.net/problem/18111 처음에 든 생각은.. 다 조사해볼 생각은 안했고.. 어떠한 것이 가장 최소 시간을 가질지 계산해보기로 했다. 당연히 모든 블럭에 대한 평균 높이로 만드는 것이 최소시간이 걸릴 것이라 생각했다. 뭐 시간이 달라서 틀린 생각이 되었고 또한 답이 같을 경우 높이가 높은 것 까지 조사해봐야 했으므로 전수조사를 해야했다. brute force란다. 처음에 틀린 풀이를 보자 #include #include using namespace std; int N, M, B; //(1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 10^7) int minh = 257; int maxh = -1; int..

백트래킹의 전형적인 문제 조건을 잘 읽어야 하는 문제 https://www.acmicpc.net/problem/15654 #맞은 풀이 #include #include #include using namespace std; int N, M; vector vec; vector ans; bool check[8]; void func(int cnt) { if (cnt == M) { for (auto v : ans) { cout > M; for (int i = 0; i > a; vec.push_back(a); } sort(vec.begin(), vec.end()); // 오름차순정렬 func(0); } 다 비슷한 문제다. 이러한 N이 다 다른 숫자가 주어져서 그렇지 만약 중..

왜 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/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..