BOJ 3114 사과와 바나나

R*C개의 칸으로 이루어진 영토가 있고 각 칸에는 사과 나무 또는 바나나 나무가 1개 이상 99개 이하 심어져 있다. 영토를 나누는데, 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래로 이동하면서 경계를 만들고, 그 경계 아래의 사과나무 개수와 경계 위의 바나나 나무 개수의 합이 최대가 되도록 하려고 한다. 경계를 만들며 이동할 때는 오른쪽, 아래쪽, 오른쪽-아래 대각선 이렇게 3가지 방향으로만 이동할 수 있고, 맨 오른쪽 아래칸까지 가야한다. 그리고 경계를 구성하는 칸의 나무의 수는 포함시키지 않는다.

다이나믹 프로그래밍이다. 처음에는 숨이 턱 막히는... 것 까지는 아녀도 거부감이 확 들었는데, 언제까지 이럴 것인가 이제 내 힘으로 풀 수 있는 문제도 좀 생겼고, 몰라도 풀이보면 웬만해서는 다 이해할 수 있지 않은가.. 즐기자 즐기자 즐기자!
 맨 왼쪽 위에서부터 시작해서 세가지 방향으로 이동하는 것을 dfs로 구현하면서... dfs+dp를 쓰면 될 것 같다. dfs + dp는 좋은데 문제는 이동하면서 아래, 위의 사과, 바나나 개수는 어떻게 알 것인가 이다.
바로 미리 각 행별로 0열부터 n열까지의 사과 나무의 개수, 바나나 나무의 개수 부분합을 각각 구해놓으면 된다. 그리고 경계를 만들면 경계를 구성하는 칸까지의 각 나무의 개수를 행 별로 얻을 수 있고 그 값들을 합하면 된다. 물론 간단하지는 않을 것이다. 대각선으로 이동하거나 아래로 이동한 경우는 간단한데, 오른쪽으로 이동했다면 같은 행이므로 조금 신경을 써야할 것이다.

그리고 d[r][c]= (r,c)를 경계의 한 칸으로 정했을 때, 경계 아래이 사과 나무, 경계 위의 바나나 나무의 개수의 합의 최대값
으로 놓으면
d[R][C] = MAX(nextR, nextC는 (R,C)로 부터 3가지 방향,
               d[nextR][nextC]+psumA[R][C-1]+psumB[R][n]-psum[C] )
일텐데, 물론 오른쪽으로 이동한 경우는 psumA, psumB를 더하는 부분에서 좀 조건을 더 넣어주든가 해야할 것이다.

일단 구현해보자!
구현하다가 문제였던 것이, 오른쪽으로 이동하는 경우인데, 만약 계속 오른쪽으로 가게 된다면 언제부터 오른쪽으로 온 것인지를... 즉, 자신의 왼쪽에 몇 개가 있는지를 알아야할 것 같았다. 그래야 그만큼을 계산안하거나 빼거나... 음 그렇다면 d[R][C][X]이렇게 3차원 배열로? 그럼 1500*1500*1500 으로... 메모리 초과가 분명해 보인다.
하지만 감사하게도 더 고민하다보니 처리할 수 있는 방법이 생각났다. 직전값이 바로 왼쪽값이면(즉, 오른쪽으로 이동한 것이라면) 직전값에서 계산했던 값에서 현재 위치의 값을 빼주기만 하면 되는 것이다. 구현해 봐야겠다.
내 구현 방식은 현재 위치에서 다음 위치로 넘어가는 것이라 아예 현재 위치에서 아무것도 더하지 않고 현재위치 값을 빼는 식으로 구현해야할 것 같다.

그리고 하나 더 예제가 안 나와서 알아봤더니, 처음에 psumA와 psumB를 구할 때, 'A'이면 psumA를 'B'이면 psumB를 계산했는데, 이렇게 하면 중간 중간 빈 공간이 생긴다. 0으로 초기화 되어있는 공간이 생긴다. 그래서 psumA는 'B'가 들어올 때는 직전값을 대입해주고, psumB는 'A'가 들어올 때 직전값을 대입해주는 연산도 추가해야 한다! 기본 중 기본이다 이건!

음 틀려서 살펴보던 중에 기저 사례를 처리하는 부분에서 맨 오른쪽 아래(R, C)에 도착했을 경우 마지막 행의 값을 return해주는데, 만약 맨 오른쪽 아래에 도착하지 않는 경우에는 어떻게 해야할지 고민하다가 그냥 NEGINF= -20억을 return하도록 ret=-2e9로 초기화 해놨다.
그런데도 틀려서 고민중이다...예제를 만들어 보던 중... 아 감사하게도 깨달았다.
감사합니다. 입력을 받을 때 숫자가 한 자리만 들어온다고 생각하고 %1d로 받고 있었다...
최대 99까지 들어오니까 그냥 %d로 받아야한다!!

그래도 틀렸다! 하지만 이번에는 또 찾아냈다. 정말로... 엄청난 실수를 했다.
오른쪽으로 이동하는 경우를 처리해주는 데서 실수했는데, 현재 위치에서 다음 위치로 넘어갈 때, 다음 위치부터의 최대값에서 현재 위치의 값을 빼주는 식으로 구현할 때, 다음 위치에서 계산한 값은 경계선이 되는 칸 왼쪽의 A의값의 합, 그리고 오른쪽의 B의 값의 합이다.
그런데 만약 현재 위치값이 B의 값이 존재한다면, 빼줄 필요가 없는 것이다! 빼면 안된다! 왜냐하면 아예 경계가 되는 칸 왼쪽의 B값은 계산하지 않았기 때문에! ...나는 여태 A값, B값을 다 뺐었는데, A값만 빼주면 된다!!!
고쳐서 제출해 봐야겠다. 와 AC를 받았다!

음 그렇게 어려운 문제는 아니겠지만 적어도 나에게는 좀 어렵고, 내 실수를 유도하는(?) 그런 문제였다. 

백준님의 풀이를 봤는데, 비슷하지만 조금 더 이해하기 쉽고 좋아보이는 방법이 있었다. 부분합을 구해놓되, 사과 나무의 부분합은 행별로, 바나나의 부분합은 열별로 구해놓고, 오른쪽으로 가는 경우에는 다음 칸에 해당하는 열의 바나나의 부분합만 더해주면 되고, 대각선으로 갈 때는, 다음 칸의 행, 열에 해당하는 사과와 바나나의 부분합을 다 더해주면 되고, 아래로 갈 때는, 다음 칸의 행에 해당하는 사과의 부분합만 더해주면 된다.

나중에 이 방법으로도 풀어봐야겠다.