글 읽기 - 0%부터 틀리는데 왜 틀리는 지 모르겠습니다.

ybc125 2년 전 0

테케도 맞고 lcs 1번 문제에서도 맞았습니다...

2시간 반째 잡고 있네요 ㅜㅜ

package boj;

import java.util.Scanner;

public class Boj_9252 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// toCharArray() : 문자열을 char[] 배열로 반환해주는 메소드
		char[] a = sc.nextLine().toCharArray();
		char[] b = sc.nextLine().toCharArray();
		int[][] dp = new int[a.length + 1][b.length + 1];
		String str = "";

		for (int i = 1; i <= a.length; i++) {
			for (int j = 1; j <= b.length; j++) {
				if (a[i - 1] == b[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		// 부분수열 구하기 시작
		int x = a.length;
		int y = b.length;

		while (x != 0 && y != 0) {
			if (a[x - 1] == (b[y - 1])) {
				str += a[x - 1];
			}
			if (dp[x - 1][y] == dp[x][y]) { // 왼쪽값과 같다
				x -= 1;
			} else if (dp[x][y - 1] == dp[x][y]) { // 윗쪽값과 같다.
				y -= 1;
			} else { // 왼쪽값과 윗쪽값과 같은 경우가 없다.
				x -= 1;
				y -= 1;
			}
		}

		if (dp[a.length][b.length] != 0) {
			System.out.println(dp[a.length][b.length]);
			for (int i = str.length()-1; i >= 0 ; i--) {
				System.out.print(str.charAt(i));
			}
		} else {
			System.out.println(0);
		}
	}
}

evade 2년 전 10

30줄에 있는 조건과 37줄의 조건을 일부러 따로 분리해놓으신건가요?

31줄의 내용을 37줄 조건 아래에 두면 정답으로 처리됩니다. 물론 package명과 class명 바꾸시구요!

현재 코드의 문제점은 같은 글자가 연속으로 나왔을 때를 생각해보시면 됩니다.

지금 짜신 코드에 대한 반례는 아래와 같습니다.

KKKBCBCAAA
KCKBCBCAKK

---- 정답 ----

KKBCBCA

---- 오답 ----

KKKBCBCA

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

문제

문제

출처

ICPC

0%부터 틀리는데 왜 틀리는 지 모르겠습니다.

ybc125 2년 전 0

evade 2년 전 10

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말