Baekjoon 9465 스티커 JAVA

해당 문제는 dp를 이용하여 해결하였다.

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%209465

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 DP를 이용해 해결하였으며 구글링의 힘을 조금 빌렸다.

먼저 문제는 2*N 행렬에 대해 상하좌우 값을 더하지 않고 대각선이나 띄어진 값을 더하여 최댓값을 찾아내면 되는 문제다.

​

조건

스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모주 찢어져서 사용할 수 없게 된다. 즉, 스티커의 왼쪽 오른쪽 위, 아랫부분은 사용할 수 없다.

먼저 배열을 생성해 입력값을 모두 넣어준 뒤 DP 배열에 값을 채워주어 dp[0][M]과 dp[1][M]중 최댓값을 출력해 주면 해결 가능하다.

​

DP 배열에 값을 채워주기 위해 젤 처음 값은 넣어주고 이후 값들은 반복문을 통해 넣어주는데 이때 대각선 값이 큰지 아니면 두 칸 띄어진 대각선 값이 큰지를 비교하여 큰 값을 넣어주면 쉽게 해결 가능하다.