백준 9251번
https://www.acmicpc.net/problem/9251

문제

---

생각하기

---

• 문자열, DP문제이다.

• 메모이제이션을 활용해서 최적화를 할 수 있다.

동작

        memo = new int[NLen + 1][MLen + 1];
        for (int i = 0; i <= NLen; i++) {
            Arrays.fill(memo[i], -1);
        }

먼저 최적화를 위해 memo배열을 사용해야 하는데
memo가 값이 저장되었는지 되지 않았는지 파악하기 위해서 -1로 초기화를 해야한다.
0은 사용해야 하는 값이기 때문에 0이 외의 방문 여부를 파악할 수 있는 값이면 되는데 여기서는 -1로 설정했다.

		...
        
        if (N.charAt(n - 1) == M.charAt(m - 1)) {
            memo[n][m] = 1 + LCS(n - 1, m - 1);
        } else {
            memo[n][m] = Math.max(LCS(n - 1, m), LCS(n, m - 1));
        }

문자열을 비교하기 위해서 2가지의 경우를 고려한다.

1. 현재 비교하는 문자가 일치할 경우
2. 현재 비교하는 문자가 일치하지 않는 경우

1.의 경우 문자가 일치하므로 각 N, M을 하나씩 넘겨 다음 문자를 비교 하면 되고,

2.의 경우에는 문자가 일치하지 않으므로 하나씩 다음 문자로 넘어가서 비교하고, 재귀를 통해서 돌아오는 값 중 가장 큰 값을 memo 배열에 저장하면 된다.

memo

[-1, -1, -1, -1, -1, -1, -1]
[-1, -1, 1, 1, -1, -1, -1]
[-1, 1, 1, 1, 2, -1, -1]
[-1, 1, 2, 2, 2, 3, -1]
[-1, 1, 2, 2, 2, 3, -1]
[-1, 1, 2, 2, 2, 3, 4]
[-1, -1, -1, 3, 3, 3, 4]

결과

코드

---

Top Down

import java.io.*;
import java.util.Arrays;

public class Main {
    
    // input
    private static BufferedReader br;

    // variables
    private static int[][] memo;
    private static String N;
    private static String M;
    private static int NLen;
    private static int MLen;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(LCS(NLen, MLen));
        return sb.toString();
    } // End of solve()

    private static int LCS(int n, int m) {
        if (m == 0 || n == 0) {
            return 0;
        }

        if (memo[n][m] != -1) {
            return memo[n][m];
        }

        if (N.charAt(n - 1) == M.charAt(m - 1)) {
            memo[n][m] = 1 + LCS(n - 1, m - 1);
        } else {
            memo[n][m] = Math.max(LCS(n - 1, m), LCS(n, m - 1));
        }

        return memo[n][m];
    } // End of topDown()

    private static void input() throws IOException {
        N = br.readLine();
        M = br.readLine();
        NLen = N.length();
        MLen = M.length();

        memo = new int[NLen + 1][MLen + 1];
        for (int i = 0; i <= NLen; i++) {
            Arrays.fill(memo[i], -1);
        }
    } // End of input()
} // End of Main class

Bottom Up

import java.io.*;
import java.util.Arrays;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static char[] chArr1, chArr2;
    private static int N, M;
    private static int[][] memo;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(bottomUp());
        return sb.toString();
    } // End of solve()

    private static int bottomUp() {
        int nIdx = 1;
        int mIdx = 1;
        while (nIdx != N + 1) {
            if (memo[nIdx][mIdx] != 0) mIdx++;

            if (chArr1[nIdx - 1] == chArr2[mIdx - 1]) {
                memo[nIdx][mIdx] = memo[nIdx - 1][mIdx - 1] + 1;
            } else {
                memo[nIdx][mIdx] = Math.max(memo[nIdx - 1][mIdx], memo[nIdx][mIdx - 1]);
            }
            
            mIdx++;
            if (mIdx == M + 1) {
                nIdx++;
                mIdx = 1;
            }
        }

        return memo[N][M];
    } // End of bottomUp()

    private static void input() throws IOException {
        chArr1 = br.readLine().toCharArray();
        chArr2 = br.readLine().toCharArray();
        N = chArr1.length;
        M = chArr2.length;

        memo = new int[N + 1][M + 1];
    } // End of input()
} // End of Main class