레아 블로그

문제 링크https://www.acmicpc.net/problem/9465 문제 설명 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내는 것이 문제!제한 조건 : 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 사용 불가 (왼, 오, 위, 아래) 문제 해결 n이 3인 2*3 개의 스티커가 있다고 가정해보자.  n=1 (2개) 점화식 dp[1][1] = arr[1][1];dp[2][1] = arr[2][1];  n=2 (4개) 점화식dp[1][2] = dp[2][1] + arr[1][2];dp[2][2] = dp[1][1] + arr[2][2]; n >= 3 점화식// 전 줄 스티커를 떼지 X 경우int diff = Math.max(dp[1][i - 2], dp[2][i..

문제 링크 : https://www.acmicpc.net/problem/2156 풀이dp를 활용한 문제이다. 이 문제에서는 "연속으로 놓여 있는 3잔을 모두 마실 수 없다." 라는 조건이 있다.  차례대로 예제를 보며 생각을 해보자.  dp[1] : 첫번째 포도주 6dp[2] : 첫번째 포도주 + 두번째 포도주 16dp[3] : 3개의 조건에서 max 값을 구한다. O O X : 두번째 와인까지 마시고 세번째 와인을 마시지 않았을 때, dp[2]O X O : 첫번째 와인 + 세번째 와인, dp[1] + wine[3]X O O : 두번째 와인 + 세번째 와인, wine[2] + wine[3]그렇다면 4번째 와인의 경우도 생각해보면 첫번째 와인 + 세번째 와인 + 4번째 와인, dp[1] + wine[3] ..

https://www.acmicpc.net/problem/1932 dp 문제 중 비교적 쉽게 풀어냈다.   아래 숫자에서 위의 숫자들 중 가장 큰 값을 가진 숫자를 더하는 식으로 dp 점화식을 세웠다.  맨 왼쪽 또는 오른쪽에 위치한 숫자들은 대각선에 있는 숫자 하나를 선택할 수 있다. 그 외에는 두 숫자 중 큰 값을 선택해 더한다. 따라서 j == 0 일 때는 dp[i-1][j] + arr[i][j]j == cnt -1 일 때는 dp[i-1][j-1] + arr[i][j] 그 외에는 Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j] 로 점화식을 세웠다.  풀이 import java.util.*;import java.io.*;public class Main {..