dp9 [백준] 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. [백준] 1149 - RGB거리 (Python) 문제 출처 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 : 이 문제 또한 DP 문제이다. 또한 다음과 같은 조건이 있다. 한마디로 말하자면 앞뒤로 집 색은 달라야 한다는 것이다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 때문에 2차원 배열을 썻고 각각 rgb에 대해서.. 2021. 3. 6. 이전 1 2 3 다음 반응형
