글 읽기 - java로 풀었습니다. 무엇을 놓친걸까요..

k94321 6년 전 0

웹에는 온통 c로작성된 답안들만 있고 java로 구현된 정답이없습니다.

저는 이걸 java로 구현했는데, 어디가 틀린것일까요?

이제 이 문제는 그만둘까봅니다..

+ 10835번입니다. 문제번호에 추가하였습니다 감사합니다 !

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class BJ_10835 {
	static BufferedReader br;
	static StringTokenizer st;
	static int N;
	static int[] left, right;
	static int[][] dp;
	static int last, AnswerN;

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("C:\\SWCert\\BJ_10835.txt"));
		br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		left = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			left[i] = Integer.parseInt(st.nextToken());
		}
		right = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			right[i] = Integer.parseInt(st.nextToken());
		}
		dp = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				dp[i][j] = -1;
			}
		}

		/* Algorithm Implementation */

		// 열 첫줄 셋팅
		for (int i = 0; i < N; i++) {
			dp[i][0] = 0;
		}

		// 행 첫줄 셋팅
		for (int i = 1; i < N; i++) {
			if (left[0] > right[i - 1]) {
				dp[0][i] = dp[0][i - 1] + right[i];
			} else {
				break;
			}
		}

		// (1,1)부터 (N,N)까지 dp 계산
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < N; j++) {
				// 1) 왼쪽을 버리는 경우
				if (dp[i - 1][j] != -1) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
				}
				// 2) 왼쪽 오른쪽을 다 버리는 경우
				if (dp[i - 1][j - 1] != -1) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]);
				}
				// 3) 오른쪽을 버리는 경우
				if (dp[i][j - 1] != -1 && left[i] > right[j - 1]) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + right[j - 1]);
				}
			}
		}

		for (int i = 0; i < N; i++) {
			AnswerN = Math.max(AnswerN, dp[N - 1][i]);
		}
		
		// N열 마지막 계산
		for (int i = 0; i < N; i++) {
			if (dp[i][N - 1] != -1 && left[i] > right[N - 1]) {
				last = dp[i][N - 1] + right[N - 1];
			}
			AnswerN = Math.max(AnswerN, last);
		}

		System.out.println(AnswerN);
	}
}

jh05013 6년 전 1

질문 번호를 넣어주세요.

그리고 입출력이나 함수 이름은 C++과 많이 다르겠지만 dp값을 계산하는 부분은 거의 비슷하다고 생각합니다.

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

문제

문제

출처

ICPC

java로 풀었습니다. 무엇을 놓친걸까요..

k94321 6년 전 0

jh05013 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말