💭 나의 접근 방법
DP 방식을 생각하지 못하고 n개의 스티커에서 다음 행 줄에서 선택할 스티커를 선택하는 방식으로 접근했다. 현재 위에 줄인경우 다음줄 아래 + 그 다음줄위 , 다다음줄 아래 중에 max인 값을 찾아서 다음 스티커로 이동할 곳을 선택해서 합을 구하는 방법으로 접근했다.
문제는 누적값을 처리하지 못하기 때문에 전체 탐색을 해서 비효율적인 접근이 되었다.
따라서, DP 를 이용해 문제를 접근해야한다.
스티커를 선택하는 방식에는
1. 한칸을 건너뛰는 경우
2. 지그재그로 가는 경우
두가지가 있다. 이 2가지를 처리하는 점화식을 만들어야한다.
한칸을 뛰는 경우는 스티커의 면을 고려했을때 현재 위에 있는 경우 전전 줄의 아래만 가능하다.
지그재그로 가는 경우는 현재 위에 있을 경우 전 줄 아래만 가능하다.
따라서 dp[위][n] += max(dp[아래][n-1],dp[아래][n-2]) 식을 도출 할 수 있다.
💡 결과
T = int(input())
for _ in range(T):
n = int(input())
dp = [list(map(int,input().split())) for _ in range(2)]
if n>1: # n=1인 경우 인덱스 오류 발생 따라서 조건식을 추가해야함
dp[0][1] += dp[1][0]
dp[1][1] += dp[0][0]
for i in range(2,n):
dp[0][i] += max(dp[1][i-1],dp[1][i-2])
dp[1][i] += max(dp[0][i-1],dp[0][i-2])
print(max(dp[0][n-1],dp[1][n-1]))하나 주의 할 점은 n=1 인경우도 있기 때문에, 초기식을 설정할때 n>1인 경우에만 초기식을 설정할수 있도록 조건식을 추가한다.
💫 느낀점
DP로 문제를 풀기 위해서는 점화식을 발견해야한다. 점화식을 발견하기 위해서는 직접 시뮬레이션을 돌려보면서 찾아보면 좋다. 위 문제와 같이 한칸을 뛰는 경우, 지그재그로 하는 경우 2가지를 발견했으므로 이러한 경우를 고려해 점화식을 도출해내는 연습이 필요할 것 같다.
https://www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
