글 읽기 - 자두문제 도움좀 부탁드리겠습니다

cjswo4034 5년 전 0

DP[i][j] : i번째 시간에 j번째 움직일 때 최대 횟수

A[i] : i번째 시간에 위치한 나무

로 정해놓고

A[i] == 1일 떄, 2일 때 j가 홀수인 경우와 짝수인 경우로 나누어서 문제에 접근해보려 했습니다..

생각한 반례나 게시판 테스트케이스를 대입해 봤을 때 맞게 나오는것 같은데 제출하자마자 마로 틀리다고 하네요

지적 환영합니다

도와주세요ㅜ

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

public class _2240 {
	static int DP[][] = new int[1001][31];
	static int A[] = new int[1001];
	static int t, w, ans;
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		t = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		A[0] = 1;

		int cnt = 1;
		for(int i = 1 ; i <= t; i++) {
			A[i] = Integer.parseInt(br.readLine());
			if(A[i] == 1) {
				DP[i][0] = cnt;
				cnt++;
			} else {
				DP[i][0] = DP[i-1][0];
			}
		}
		
		for(int i = 1 ; i <= t; i++) {
			for(int j = 1 ; j <= w; j++) {
				if(A[i] == 1 && j % 2 == 0) {
					if(A[i-1] == 1)	DP[i][j] = DP[i-1][j]+1;
					else if(A[i-1] == 2) DP[i][j] = DP[i-1][j-1]+1;
				} else if(A[i] == 2 && j % 2 == 1) {
					if(A[i-1] == 1)	DP[i][j] = DP[i-1][j-1]+1;
					else if(A[i-1] == 2) DP[i][j] = DP[i-1][j]+1;
				} else {
					DP[i][j] = DP[i-1][j];
				}
			}
		}
		
		for(int i = 0 ; i <= w; i++) {
			ans = Math.max(ans, DP[t][i]);
		}
		System.out.println(ans);
	}
}

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

문제

문제

출처

ICPC

자두문제 도움좀 부탁드리겠습니다

cjswo4034 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말