백준: 27890 (문자열 게임) [JAVA]

문제 링크

https://www.acmicpc.net/problem/27980

27980번: 문자열 게임

 

풀이

전체적인 풀이 과정은 다음과 같다.

1. 보드의 문자와, 가지고 있는 문자열을 입력 받고 dp용 2중 배열을 생성
2. 탐색 함수를 구현 (인자의 경우 보드의 문자와 문자열, 그리고 각각의 특정 위치를 담당하는 인덱스)
   1) 문자열이 끝에 도달했다면 0 반환 (기저조건)
   2) 기존의 연산값이 존재한다면 해당 값 반환
   3) 보드에서 왼쪽에 갈 수 있다면, 탐색 함수를 호출
   4) 보드에서 오른쪽으로 갈 수 있다면, 해당 탐색 함수를 호출해 그 중 최대값을 저장
   5) 이후 현재 문자가 같다면 점수 +1
   6) 결과를 dp 배열에 저장하며 반환
3. 앞서 구현한 탐색 함수를, 보드 속 시작 위치를 모두 다르게 하여 함수를 호출하고 그 중 최고 점수를 출력

 완전 탐색으로 점수를 계산하면서, dp를 활용해 탐색의 중복을 줄인다. 우선 보드의 문자와, 가지고 있는 문자열을 입력받고 dp를 위한 2중 배열을 생성한다.

 그리고 다음엔 완전 탐색을 위한 함수를 구현하는데, 우선 인자는 보드의 문자와 가진 문자열, 그리고 각각의 문자열 속 특정 위치를 나타내는 인덱스다. 함수의 기저조건은 우선 가진 문자열이 끝에 도달한 경우로, 0을 반환한다. 이후 해당 함수 계산 값이 이미 존재한다면, 해당 값을 반환한다. 그리고 나서는 최대 두 가지 경우를 비교하여 그 중 최대 점수를 확인하면 된다. 보드에서 왼쪽으로 갈 수 있는 경우와 보드에서 오른쪽으로 갈 수 있는 경우에 대하여 그 중 최대 점수를 가져온 다음, 현 위치의 문자가 같다면 점수를 +1 해준다. 이후엔 현재 결과를 dp 배열에 저장하며 반환하면 된다.
 이후엔 단순히 해당 함수를 호출하여 탐색을 진행하면 되는데, 이 때 다양한 상황을 위해 보드 속 시작 위치를 모두 다르게 하여 탐색을 진행한다. 이후엔 저장된 최대 점수를 출력하면 된다.

 

public class Solution {

    static int[][] memory;
    public static void main(String[] args) throws IOException {
        int maxPoint = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        memory = new int[N][M];

        for (int i = 0; i < N; i++) {
            Arrays.fill(memory[i], -1);
        }

        String boardString = br.readLine();
        String string = br.readLine();

        for (int i = 0; i < N; i++) {//보드 속 시작 위치를 모두 다르게
            maxPoint = Math.max(maxPoint,
                    check(N, M, boardString, string, i, 0));
        }

        System.out.println(maxPoint);
    }

    static int check(int N, int M, String boardString, String string, int boardStringIndex, int stringIndex) {
        if (stringIndex == M) {//기저 조건
            return 0;
        }

        if (memory[boardStringIndex][stringIndex] != -1) {//기존 연산값 존재
            return memory[boardStringIndex][stringIndex];
        }

        int point = 0;

        if (boardStringIndex > 0) {//보드에서 왼쪽으로 갈 수 있다면
            point = check(N, M, boardString, string, boardStringIndex - 1, stringIndex + 1);
        }

        if (boardStringIndex < N - 1) {//보드에서 오른쪽으로 갈 수 있다면
            point = Math.max(point, check(N, M, boardString, string, boardStringIndex + 1, stringIndex + 1));
        }

        if (boardString.charAt(boardStringIndex) == string.charAt(stringIndex)) {//현 위치의 문자가 같다면
            ++point;
        }

        return memory[boardStringIndex][stringIndex] = point;
    }
}

결과