[BOJ/C++] 9465: 스티커

🥈 Silver 1

✏️ 1차 솔루션

1. 모든 자리에서 현재 위치와 상하좌우 값들 중에 최대값을 찾고 최대값의 상하좌우를 갈 수 없는 자리로 방문 처리
   1) 현재 위치가 최대값일 경우, 현재 위치의 상하좌우를 방문처리
   2) 최대값이 따로 있을 경우, 해당 위치로 옮겨서 현재 위치가 최대값이 될 때까지 반복
2. 모든 위치에 대해 탐색하면 최대값을 산출할 수 있는 위치만 visited 처리되지 않기 때문에 visited 처리 되지 않은 위치의 값을 모두 더해줌

🚨 1차 trouble

시간초과
DP 문제이지만 DP로 접근을 못하겠어서 이렇게 풀었음

✏️ 최종 솔루션

⭐️ DP 로 풀이

❗️ 첫번째 열과 마지막 열의 스티커는 2행 중 하나는 무조건 뜯게 되어있음
⭐️ 현재 위치를 뜯을 수 있는 경로에서 뜯은 최대 스티커값을 DP에 저장하는 원리
➡️ 일단 현재 위치는 무조건 뜯는다는 전제하에 최대값을 산출하는 것
➡️ 이렇게 되면 마지막 열에 최대값이 모이게 됨

1. 스티커를 뜯을 때는
   1) 대각선 바로 위를 뜯고 현재 위치 뜯기
   2) 대각선 바로 위의 왼쪽 스티커를 뜯고 현재 위치 뜯기
   ➡️ 이 두가지 방법밖에 없기 때문에 이 중에 큰 DP 값을 취하기

dp[0][i]=max(dp[1][i-1], dp[1][i-2]) + score[0][i];
dp[1][i]=max(dp[0][i-1], dp[0][i-2]) + score[1][i];

2. (0,n), (1,n) 의 dp 값 중에 큰 값을 정답으로 산출

📌 self feedback

현재 위치를 무조건 뜯는다는 전제 하에 앞서서 뜯을 수 없는 최대값을 DP에 저장한다는 방식으로 접근해야했음
이렇게 하면 앞에서 어떤 루트가 가장 최대값을 만드는가와는 별개로 값을 산출하다가 최종적으로는 마지막 열에서 1행으로 끝나느냐 2행으로 끝나느냐 중에 최대값을 고르면 최종 최대값을 산출할 수 있음