다이나믹프로그래밍8 [백준] 1912 - 연속합 (Python) 문제 출처: www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이: DP문제이다. DP문제에선 점화식을 어떻게 세우는지가 가장 중요하다. 우선 DP[i] = i 번째에서 얻을 수 있는 최대합으로 설정하였다. 그런데 이런경우엔 음수가 껴있기 때문에 끝까지 돌았을 경우 최대값을 구할 수 없을 수 있다. DP[i]는 DP[i-1]에 arr[i]를 더할지 아니면 더하기를 끊고 새롭게 DP[i]값을 갱신할지를 생각하기 때문에 기존의 최대값을 반영할 수 없다는 점이 있다. .. 2021. 3. 20. [백준] 11727 - 2xn 타일링2 (Python) 문제 출처: www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀이: 앞서 본 2xn 타일링 과 매우 흡사한 문제이다. 이문제의 경우 기존에 문제에 2x2타일이 생긴 경우이다. 정답을 듣기전에는 사고하기가 어려울 수 있는데 간단하게 생각하면 기존 2xn 타일링 문제의 점화식을 그대로 가져오되, 2x2 짜리 타일은 1x2짜리 타일 2개를 이은거와 같은 형태이므로 2x2 타일을 쓸 경우와, 1x2짜리 타일을 쓸 경우를 따로 샌다고 생각해보면 두가지다 결국 dp[n-2] 가 된다. 따라서 .. 2021. 3. 17. [백준] 11726 - 2xn타일링 (Python) 문제 출처 : www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 : 문제를 읽어보면 DP의 냄새가 물씬 난다. DP의 핵심은 (나도 아직 잘 못하지만) 남에게 미루기 라고 생각한다. 이 문제에서는 놓을 수 있는 블록이 2x1 이랑 1x2 짜리 2개이다. 그러면 점화식을 다음과 같이 놓을때, dp[n] = 1xn 에 타일을 놓을 수 있는 방법의 수 이런 경우에 우리는 맨마지막에 2x1을 넣을지 1x2를 넣을지 생각해 볼 수 있다. 즉 우리는 dp[n] 에 대해서 dp[n].. 2021. 3. 17. [백준] - 1932 정수 삼각형 (Python) 문제 출처 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이: 우선 이 문제 같은경우는 다음과 같은 조건을 고려해서 점화식을 짜야한다. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 여느 DP 문제와 같이 점화식을 먼저 세워봣다. DP[i] = level i에서 얻을 수 있는 최대 합 이라고 생각하고 각각의 경우를 생각해봣다. (단, tri는 삼각형의 수를 들고 있는 자료구조) 이후 다음과 같이 각 단계에 대한 DP를 생각해보니 DP를 2차원으로 짜야.. 2021. 3. 6. 이전 1 2 다음 반응형
