본문 바로가기
반응형

Problem Solving242

백준 1099번 알 수 없는 문장 - C++(cpp) 풀이 1. dp(idx): 부분 문자열 sentence[idx...]를 해석하는 최소 비용 2. dp(idx) = min(앞부분을 단어 word에 매칭 하는 비용 + dp(idx+word.size())) 3. 단어 매칭 비용 계산도 메모이제이션하여 시간을 절약한다. 1. dp(idx): 부분문자열 sentence[idx...]를 해석하는 최소 비용 앞부분을 어느 단어와 매칭 시키느냐에 따라 뒷부분을 해석하는 비용이 달라지므로 다이나믹프로그래밍을 사용하여 구할 수 있다. dp(idx)를 위와 같이 정의하면, 총 구해야 하는 dp값은 문장의 길이와 같으므로 총 N=50개가 된다. 2. dp(idx) = min(앞 부분을 단어 word에 매칭 하는 비용 + dp(idx+word.size())) 앞 부분을 단어로 매.. 2022. 4. 13.
백준 1030번 프렉탈 평면 - C++(cpp) 풀이 1. fill(sz, sr, sc) = 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로 하고 크기가 sz x sz인 부분 채우기 2. 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다. 3. N*N개 조각으로 나눈 뒤, fill을 재귀적으로 호출해 나머지 부분의 색칠을 완료한다. 1. fill(sz, sr, sc) = 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로 하고 크기가 sz x sz인 부분 채우기 프렉탈 무늬가 재귀적으로 생성되므로 분할정복을 이용할 수 있다. fill(sz, sr, sc)를 다음과 같이 정의하자. 2. 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다. fill에서는 현재 보드를 N*N개 조각.. 2022. 4. 12.
백준 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.
반응형

티스토리툴바