BOJ-17351 3루수는 몰라

필요한 지식

1. 동적계획법

접근

• 그래프 탐색으로 가능한 모든 문자열을 탐색 후 각 문자열을 검사해 주면 시간초과 & 메모리초과 이다.

• dp[i][j]의 값은 dp[i][j]로 올 수 있는 dp[i][j-1] 과 dp[i-1][j]의 값중 최대 값을 저장한다.

• dp[i][j]에 값을 넣어 줄 때 go()함수를 이용해 현재(i,j)까지 진행했을 때 MOLA를 만들 수 있는지 검사한다.

int go(int y, int x, int cnt) { // 행,열,MOLA 문자열 카운트
	if (!y || !x) return 0;
	if (arr[y][x] == str[cnt]) {
		if (!cnt) return dp[y][x] + 1;
		return max(go(y - 1, x, cnt - 1), go(y, x - 1, cnt - 1));
	}
	return 0;
}

• 현재 좌표로부터 4번 거슬러 올라갔을 때 MOLA문자열이 존재한다면 M까지 거슬러 올라간 위치에 저장되어있는 값에 1을 더한값을 반환하고 현재좌표에 반영한다.

코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
char arr[501][501];
int dp[501][501];
string str = "MOLA";
int go(int y, int x, int cnt) {
	if (!y || !x) return 0;
	if (arr[y][x] == str[cnt]) {
		if (!cnt) return dp[y][x] + 1;
		return max(go(y - 1, x, cnt - 1), go(y, x - 1, cnt - 1));
	}
	return 0;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		string s; cin >> s;
		for (int j = 1; j <= n; j++) {
			arr[i][j] = s[j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i - 1][j], max(dp[i][j - 1], go(i, j, 3)));
		}
	}
	cout << dp[n][n];
	return 0;
}