반응형 전체 글282 백준 14462번 소가 길을 건너간 이유 8 - C++(cpp) 풀이 1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 2. dp(l, r) = left_cows[l...]과 right_cows[r...] 사이에 놓을 수 있는 횡단보도의 최대 개수 3. dp(l, r) = max(왼쪽의 l번째 소는 연결하지 않는 경우, 왼쪽의 l번째 소와 오른쪽의 i번째 소와 연결하는 경우) 1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 왼쪽 목초지의 소를 기준으로 차례로 연결한다고 하면, 횡단보도가 겹치지 않기 위해서는 연결시키는 오른쪽 목초지의 소도 오름차순이어야 한다. 즉, 더 나중에 매칭하는 오른쪽 소의 번호가 작아지면 안 된다. 이전 매칭에서 최대한 앞쪽의.. 2022. 4. 17. 백준 13418번 학교 탐방하기 - C++(cpp) 풀이 1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다. 2. 오르막길에는 가중치 1, 내리막길에는 가중치 0을 준다. 3. 최악의 경로는 최대 스패닝 트리, 최적의 경로는 최소 스패닝 트리이다. 1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다. 모든 건물을 방문하는 데 필요한 최소한의 길을 선택해야 한다. 즉, 최소 연결 부분 그래프 = 스패닝 트리를 구하면 된다. 모든 건물을 방문하려면 왔던 길을 되돌아가야 하기 때문에 문제가 생기지는 않을까 싶지만, 오르막길은 되돌아갈 때는 내리막길이 되고, 또 내리막길이 되돌아올 때 오르막길이 되는 것은 무효 처리하기 때문에 단순히 스패닝 트리를 구해도 문제가 되지 않는다. 2. 오르막길에는 가중.. 2022. 4. 15. 백준 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. 이전 1 ··· 27 28 29 30 31 32 33 ··· 57 다음 반응형
