글 읽기 - 어디가 틀린건지 모르겠습니다.. 알려주시면 감사하겠습니다.ㅠ

tjdwlsdl 7년 전 0

DP 배열을 만들어서 1~N 번째 까지 값을 넣습니다.

[0][i]번 째 DP는 DP[0][i-2]와 DP[1][i-2]와 DP[1][i-1]를 비교하여 가장큰 값과 [0][i]번 째 값을 더해서 [0][i]번 째 DP에 넣습니다.

마지막에는 [0][N]와 [1][N]을 비교해서 큰 값을 출력했습니다.

제출하면 틀렸다고 나오는데 여러번 코드도 보고 반례도 찾아보려고 했지만 못찾겠습니다.

읽어주셔서 감사하고 잘못 코딩한 곳이나 반례를 찾아주시면 감사하겠습니다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        // 테스트 케이스
		int t = Integer.parseInt(br.readLine());
		while(t-->0){
            // 배열의 길이
			int n = Integer.parseInt(br.readLine());
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			StringTokenizer st2 = new StringTokenizer(br.readLine());
            // 테이블겸 dp배열
			int[][] dp = new int[2][n+1];
			int j = 1;
			while(st1.hasMoreTokens()){
				dp[0][j] = Integer.parseInt(st1.nextToken());
				dp[1][j] = Integer.parseInt(st2.nextToken());
				j++;
			}
            // 0번 째와 1번 째 각각 넣는데
            // i-2번 째의 0번과 1번 값과 i-1번 째의 0번이면 1번을 1번이면 0번값을 
            // 비교해서 가장큰 값을 i번째에 넣기
			for(int i = 2; i <= n; i++){
				dp[0][i] += max(dp[0][i-2],dp[1][i-2],dp[1][i-1]);
				dp[1][i] += max(dp[0][i-2],dp[1][i-2],dp[0][i-1]);
			}
			sb.append(dp[0][n]>dp[1][n]?dp[0][n]:dp[1][n] + "\n");
		}
		System.out.print(sb.toString());
	}
    // a,b,c중 가장 큰 값 반환
	static int max(int a, int b, int c){
		return a>b?a>c?a:c:b>c?b:c;
	}
}

tjdwlsdl 7년 전 0

@cubelover 님 댓글 남겨주셔서 감사합니다.

덕분에 맞았습니다!

그리고 죄송하지만 혹시 차이점도 알려주실수 있으신가요?

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

문제

문제

출처

ICPC

어디가 틀린건지 모르겠습니다.. 알려주시면 감사하겠습니다.ㅠ

tjdwlsdl 7년 전 0

tjdwlsdl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말