[C++] 백준 17351번 3루수는 몰라

문제

운동장은 N×N 크기의 격자로 표현된다.

운동장의 각 칸에는 알파벳 대문자로 표현되는 단서들이 숨겨져 있다.

우리는 (1, 1)에서 (N, N)까지 이동하면서 단서를 수집해야 한다. (각 좌표는 시작점과 도착점이다.)

지금은 여름이라 몹시 더우므로, (r+1, c) 또는 (r, c+1)로만 움직여야 한다. (안 그러면 탈진해서 쓰러질 것이다!) 물론, 운동장을 벗어날 수는 없다.

운동장을 지나면서 수집한 단서를 순서대로 이어 붙인 문자열을 S라고 하자. S에 "MOLA"라는 부분 문자열이 최대한 많이 등장하도록 움직여야 한다.

어떤 칸을 지나면 반드시 해당 칸의 단서를 수집해야 한다. 즉, 단서를 취사 선택하지 않는다.

입력

첫째 줄에 운동장의 크기 N이 주어진다. (1 ≤ N ≤ 500)

둘째 줄부터 N개의 줄마다 N개의 문자가 주어진다. 이는 운동장 각 칸의 단서를 적어둔 지도이며, 알파벳 대문자로만 이루어져 있다.

첫 줄의 첫 문자가 (1, 1)이고, 마지막 줄의 마지막 문자가 (N, N)이다.

출력

주어진 규칙을 따라 이동하면서 부분 문자열로 "MOLA"를 최대한 많이 포함하는 S를 만들고, 이때 S에 포함된 부분 문자열 "MOLA"의 개수를 출력한다.

풀이

solve 함수는 MOLA의 완성정도가 str일때 (x,y)지점에서 (n-1,n-1)지점까지 갈 때 만들 수 있는 최대 MOLA의 개수를 리턴한다. 문제에서는 n,n이라 나왔지만 편의상 (0,0)~(n-1,n-1)로 가정하고 풀었다. str은 MOLA의 완성정도를 나타내는 매개변수로서
다음칸이 M일때 str=1, O일때 str=2 등과 같이 표현하였다. (0,0)이 M인 경우와 아닌 경우 str값이 달라지므로 이를 구분하여 풀어주면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n;
string board[505];
int dp[505][505][4];
int dx[2] = {1,0};
int dy[2] = {0,1};

// x,y에서 n-1,n-1까지 갈 때 만들 수 있는 몰라 개수, str 완성정도
int solve(int x, int y, int str){
  if (x == n-1 && y == n-1) return 0;

  int &ret = dp[x][y][str];
  if (ret != -1) return ret;
  ret = 0;

  for (int i=0; i<2; i++){
    int nx = x+dx[i];
    int ny = y+dy[i];
    if (nx < 0 || nx > n-1 || ny < 0 || ny > n-1) continue;

    if (board[nx][ny] == 'M'){
      ret = max(ret, solve(nx,ny,1));
    }
    else if (board[nx][ny] == 'O' && (str == 1)){
      ret = max(ret, solve(nx,ny,2));
    }
    else if (board[nx][ny] == 'L' && (str == 2)) {
      ret = max(ret, solve(nx,ny,3));
    }
    else if (board[nx][ny] == 'A' && (str == 3)){
      ret = max(ret, solve(nx,ny,0)+1);
    }
    else ret = max(ret, solve(nx,ny,0));
  }

  return ret;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++)
    cin >> board[i];

  memset(dp, -1, sizeof(dp));

  if (board[0][0] == 'M') cout << solve(0,0,1);
  else cout << solve(0,0,0);
  
}