노는 게 제일 좋아

어려웠다. 부분으로 쪼갤 수 있었지만 생각이 잘 안났다. https://www.acmicpc.net/problem/9251 모든 부분을 부분수열로 쪼개보니.. for문이 3개나 나와서 그냥 떄려쳤다. DP문제라는 것을 한 번에 파악할 수 있었다. 어떻게 전체 문제를 부분으로 쪼갤 수 있을까 고민했다. 처음에는 맨앞에서부터 접근했지만 틀린 접근법이었다. 마지막부터 조사했어야 했다. 길이가 L1, L2의 문자열이 있다. 만약 마지막 부분이 같다면 해당 마지막부분을 제외한 채로 나머지 L1 -1 , L2 - 1의 문자열의 가장 긴부분을 조사하면 될 터였다. 마지막 부분이 다르다면 둘 다 제외하는 것이 아닌 L1 - 1, L2 또는 L1, L2 - 1의 문자열을 조사하면되었다. 그리고 문자열이 비어있는 것과의 ..

용량도 작다 https://www.acmicpc.net/problem/2293 심히 기분이 좋지 않다. 재귀로 푸는 방법을 알았지만.. 용량도.. 시간도 초과할 것이 뻔했다. 다른 방법을 찾는데.. 너무 헤맸다. 이러한 방법은 정말 많은데 충분히 익혀놔야할 방법 중 하나같다. 하향식보다 이번엔 상향식으로 하는 것이 맞았다.dp에 저장해가며 푸는 것이 이 문제의 핵심이었을 것이다. #include using namespace std; int n,k; int coin[101]; int dp[100001]; int main(){ cin >> n >> k; for(int i = 1; i> a; coin[i] = a; } //dp[0] = 1 을 추가시켜주어야함 //첫번째 코인으로 만들 수 있는 경우의 수를 추가..

다이나믹 프로그래밍이 재밌어지는 시기 https://www.acmicpc.net/problem/2193 우선 예를 몇개 들고나보면 하위 문제로 쪼개지는 것을 알 수 있고 하위 문제에 대해 답을 구하면 된다. 재귀함수로 구현을 해보고 해당 함수를 Memoization 하게되면 시간 안에 풀어진다. #include using namespace std; int N; long long dp[91][2]; int main(){ cin >> N; dp[1][1] = 1; dp[2][0] = 1; for(int i = 3; i

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/17298 이것은 그냥 뭐 생각대로 하기 쉽지 않다. 해보려 했는데..인덱스가 저장이 안되어서 정말 힘들었다.그래서 pair를 쓸까 하다가.그냥 스택 2개를 썼다. 인덱스를 이용해야 한다라는 생각을 하면 어렵지만 생각할 수 있는 문제라고 한다.한 번에 생각하기는 확실히 힘든 것 같다. 다른 사람과 풀이를 비교하지 않는 이유는원리는 같아서 그렇다. #include #include #include #include using namespace std; stack num; // 숫자를 넣음 stack stk; // 인덱스를 넣음 int N; int arr[1000001]; void init(){ io..

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/1260 이것은 그냥 뭐..그냥 구현하면 된다. 다만 여기서 주의할 점은 방문을 언제할 것이냐를 판단하느냐 문제다. 나머진 어렵지 않다. 그냥 머릿속에서 생각하는 그대로 구현한다. #include #include #include using namespace std; int N, M, V; // 정점, 간선, 시작 노드 int map[1001][1001]; int visited[1001]; int backup[1001]; queue Q; stack S; void copy(int origin[1001], int backup[1001]) { for (int i = 1; i > N >> M >> V;..

바로 생각한 대로 실행하면 되는 문제다. https://www.acmicpc.net/problem/2003 우선 N~M번째 까지의 합은 1~M - 1~N-1 인것을 나는 이용했다. 하지만 이제부터는 잘한 사람들에게서도 나와 무엇이 다른지 공부하기로 했다 우선 나의 풀이를 보고 다른 잘한 사람들의 풀이를 비교해보자 #맞은 풀이 #include using namespace std; int N,M; int arr[10001]; int dp[10001]; // dp[i] -> 1~i번째까지의 합 // N~M 까지의 합은 1~M번째 까지의 합 - 1~N-1 번째까지의 합. int main(){ cin >> N >> M; int cnt = 0; for(int i=1; i> arr[i]; dp[i] = dp[i-1]..

https://www.acmicpc.net/problem/1094 처음에 생각했을 때.. 이진법? 생각났다. 문제를 읽고 예를 읽어보니 맞다. 즉, 이진법 수에서 1의 개수를 구하는 문제다. 즉, 우리가 이진법 변환을 어떻게 했는지 생각해봤다. 2로 나누면서 나머지를 세었다. 마지막까지 2로 나누어서 숫자를 판단했다. 코딩도 그렇게 했다. #include using namespace std; int N; int main() { cin >> N; int sum = 0; while (N >= 1) { sum += N % 2; N /= 2; } cout

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