반응형 전체 글282 백준 5175번 문제없는 문제 - C++(cpp) 풀이 1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. 2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다. 1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N개 문제 중에서 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N=20이므로 총 2^20가지의 경우가 있고 이는 시간 내에 모두 탐색할 수 있다. 2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다. 이제 모든 경우를 크기 순, 사전 순으로 탐색하면서 최초로 M개의 알고리즘을 모두 커버하는 경우를 찾아내면 된다. 크기 순, 사전 순으로 정렬하기 위해 각 경우를 비트마스크로 나타내고 1의 .. 2022. 4. 11. 백준 13398번 연속합 2 - C++(cpp) 풀이 1. dp[idx][did_remove] = 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합 2. dp[idx][1] = max(arr[i], arr[i]+dp[i+1]) 3. dp[idx][0] = max(arr[i], arr[i]+dp[i+1][0], arr[i]+dp[i+2][1]) 1. dp[idx][did_remove] = 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합 연속합은 재귀적으로 생각할 수 있다. 또한 숫자를 최대 한 개까지 제거할 수 있으므로 dp[idx][did_remove]를 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합이라고 정의하자. 2. dp[idx][1] = max(arr[i.. 2022. 4. 8. 백준 2650번 교차점개수 - C++(cpp) 풀이 1. 세 개 이상의 연결선이 한 점에서 만나지 않으므로, 교차하는 선분 쌍의 개수가 곧 교차점의 개수이다. 2. 한 선분이 다른 선분을 완전히 포함하는 경우에는, 교차하지 않는 것으로 판정한다. 3. 모든 선분 쌍에 대해 교차 여부를 구하면서 총 교차점 수와 최대 교차점 수를 구한다. 1. 세 개 이상의 연결선이 한 점에서 만나지 않으므로, 교차하는 선분 쌍의 개수가 곧 교차점의 개수이다. 두 점을 직선으로만 잇는다면 세 개의 선분 A, B, C가 한 점에서 만날 수 있다. 이때 선분 쌍 AB, BC, 그리고 CA가 교차한다. 그런데 세 개 이상의 선분을 한 점에서 만나도록 하면 안 된다. 즉 각 선분 쌍이 모두 다른 점에서 만나도록 해야 하므로, 선분 쌍의 개수가 곧 교차점의 개수와 같게 된다. 2. .. 2022. 4. 7. 백준 5557번 1학년 - C++(cpp) 풀이 1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자. 2. dp(val, idx) = dp(val+arr[idx], idx+1) + dp(val-arr[idx], idx+1) 이다. 3. 최종적으로 구해야하는 값은 dp(arr[0], 1)이다. 1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자. 백트래킹으로 풀이하게되면, 최대 2^98번을 탐색하므로 시간초과가 발생한다. 중간 계산값이 0 이상 20 이하로 제한되어 있으므로 DP를 이용해서 풀이할 수 있다. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수부터 고려할 때 .. 2022. 4. 6. 백준 1405번 미친 로봇 - C++(cpp) 풀이 1. DFS로 모든 경우 4^N가지를 다 고려한다. 2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다. 1. DFS로 모든 경우 4^N가지를 다 고려한다. N이 작기 때문에 모든 경우를 다 고려하는 방법을 생각해볼 수 있다. N=14이므로 모든 경우의 수는 4^14 = 268,435,456이 된다. 중간에 방문했던 곳을 또 방문했을 경우 가지치기가 되므로 실제 탐색 횟수는 이것보다 더 적어진다. 2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다. N칸을 이동했을 때 해당 루트로 이동할 확률은 매 이동마다 해당 방향으로 이동할 확률의 곱과 같다. dfs에서 매 depth마다 이동 확률을 누적해서 전달해주면 된다. #include #include #include using nam.. 2022. 4. 5. 이전 1 ··· 28 29 30 31 32 33 34 ··· 57 다음 반응형
