글 읽기 - LCS 배열 차이

myoungs14 4년 전 0

제 생각엔 LCS 알고리즘과 차이가 없다고 생각되는데 계속해서 답이 이상하게 나오네요

마지막 for문은 dp가 어떻게 되어있나 체크하려고 넣었습니다.

혹시 chatAt과 / 입력받은 readLine을 char배열로 만든것을 비교하는 것이 차이가 있나요 ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class bj_9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int[][] dp = new int[str1.length + 1][str2.length + 1];

        for (int i = 1; i <= str2.length; i++) {
            for (int j = 1; j <= str1.length; j++) {
                if (str2[i - 1] != str1[j - 1])
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                else
                    dp[i][i] = dp[i - 1][j - 1] + 1;
            }
        }
        bw.write(String.valueOf(dp[str1.length][str2.length]) + "\n");
        for (int a[] : dp) {
            for (int b : a)
                bw.write(String.valueOf(b) + " ");
            bw.newLine();
        }

        br.close();
        bw.close();
    }
}

djm03178 4년 전 1

1. 13, 23번째 줄에서는 dp 배열이 [str1][str2]와 같이 구성되어 있는데 15~22번째 줄은 전부 [str2][str1] 관련으로 접근하고 있습니다.

2. 20번째 줄에서 dp[i][i]를 dp[i][j]로 바꿔야 합니다.

그 후 디버깅 코드 지우시고, 클래스 이름을 Main으로 바꾸면 통과됩니다.

myoungs14 4년 전 0

@djm03178님 감사합니다!!

맞네요 ㅠㅠ 초기 설정 str1 str2 길이로 만든걸 생각안하고 계속해서 반복문만 바꾸니 틀리게 나왔네요ㅜㅜ

잘해결되었습니다! 감사드려요 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

LCS 배열 차이

myoungs14 4년 전 0

djm03178 4년 전 1

myoungs14 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말