글 읽기 - 무엇인 틀린 건가요..?

tmvld9 5년 전 0

안녕하세요 ?

잠을 자려고 했지만, 테스트케이스가 다 맞고 다른 반례도 다 맞아서 질문드립니다 !!

혹시 무엇이 틀렸나요..?

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

class Sticker {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int t, n;
	int[][] arr;
	int[][] dp;
	Sticker(){
		try {
			t = Integer.parseInt(br.readLine());
		}catch(IOException ie) {}
	}
	void input() {
		try {
			n = Integer.parseInt(br.readLine());
			arr = new int [3][100001];
			dp = new int [3][100001];
			int x=1;
			while(x<3) {
				String line = br.readLine();
				StringTokenizer st = new StringTokenizer(line, " ");
				for(int i=1; i<=n; i++) {
					arr[x][i] = Integer.parseInt(st.nextToken());
				}
				x++;
			}
		}catch(IOException ie) {}
	}
	void loop() {
		dp[1][1] = arr[1][1];
		dp[2][1] = arr[2][1];
		for(int i=1; i<=n; i=i+2) {
			dp[1][i+2] = dp[1][i]+Math.max((arr[2][i+1] + arr[1][i+2]), arr[2][i+2]);
			dp[2][i+2] = dp[2][i]+Math.max((arr[1][i+1] + arr[2][i+2]), arr[1][i+2]);
		}
	}
	int checkMax() {
		int max =0;
		for(int i=1; i<=2; i++)
			for(int j=n; j<=n+1; j++)
				max = Math.max(dp[i][j], max);
		return max;
	}
	void play() {
		while(t-->0) {
			input();
			loop();
			System.out.println(checkMax());
		}
	}
}

class Main{
	public static void main(String[] args) {
	  new Sticker().play();
	}
}

djm03178 5년 전 0

dp의 의미를 확실히 하셔야 합니다. 예를 들어 지금 코드에서는 dp[2][3]이라는 건 arr[2][3]의 스티커를 사용했을 수도 있고 사용하지 않았을 수도 있는데, 그렇다면 dp[2][3] 다음에 arr[2][4]를 사용할 수 있는지 없는지 여부는 어떻게 판단할까요?

tmvld9 5년 전 0

djm03178님 !

제가 메모이제이션을 사용해야 하는데, 그냥 예측을 해버렸네요 ! 왜 다른 분들이 다 -2를 썼는지 이제야 알겠습니다 !! 감사합니다 !

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

문제

문제

출처

ICPC

무엇인 틀린 건가요..?

tmvld9 5년 전 0

djm03178 5년 전 0

tmvld9 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말