본문 바로가기
반응형

Problem Solving/BOJ228

백준 10986번 나머지 합 - C++(cpp) 풀이 1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면, psum[e] % M = psum[s-1] % M이어야 한다. 2. psum[i] % M = psum[j] % M 인 (i, j) 쌍의 개수를 구한다. 3. psum[i] % M 자체가 0인 경우도 추가로 카운트한다. 1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면,psum[e] % M = psum[s-1] % M이어야 한다. i까지의 누적합을 psum[i]라고 하자. s부터 e까지의 구간합은 psum[e] - psum[s-1]이 된다. 이 구간합이 M으로 나누어 떨어지려면, (psum[e] - psum[s-1]) % M = 0이어야하므로, psum[e] % M = psum[s-1] % M이 성립해야 한다. 2. psum[i] % M = p.. 2022. 4. 14.
백준 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.
반응형

티스토리툴바