글 읽기 - 어디서 틀린걸까요??

hanjh04 7년 전 0

안녕하세요, 어디가 잘못된건지 못찾아서 질문드립니다.

점화식은

입력받은 수를 ar[]에 저장했을 때,

dp[1][1] = ar[1]로 넣고

1.j = 1일때

dp[i][j] = max(dp[i-1][j], max(sum(i~1)))

2. j != 1 일때

dp[i][j] = max(dp[i-1][j], max(dp[i-2][j-1], dp[i-1][j])+ar[i])

요렇게 세웠어요

테스트케이스로 주어진거랑, 제가 몇개 만들어서 해봤는데 어디가 잘못됐는지 못찾아서 질문올려요. 감사합니다!!!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
 static int N, M;
 static int[][] dp;
 static int[] ar;
 public static void main(String[] args) throws Exception {
  // TODO Auto-generated method stub
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     //N, M 입력
  String[] tmp = br.readLine().split(" ");
  N = Integer.parseInt(tmp[0]);
  M = Integer.parseInt(tmp[1]);
      //dp, ar 초기화
  dp = new int[N + 1][M + 1];
  ar = new int[N + 1];
     //ar[]에 값 집어넣기
  for (int i = 0; i < N; i++) {
   ar[i + 1] = Integer.parseInt(br.readLine());
  }
  int tmp1, tmp2 = Integer.MIN_VALUE;
  int sum;
     //답 구하기 시작
  dp[1][1] = ar[1];
  for (int i = 2; i <= N; i++) {
   for (int j = 1; j <= Math.min(Math.ceil(i / 2), M); j++) {
    if(j == 1){
     // i번째 수가 추가되지 않는 경우
     tmp1 = dp[i - 1][j];
     // i번째 수가 추가되는 경우
     tmp2 = Integer.MIN_VALUE;
     for (int k = 1; k <= i; k++) {
      sum = sum(k, i);
      tmp2 = tmp2 > sum ? tmp2 : sum;
     }
     dp[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
     
    }else{
     //i번째 수가 추가되지 않는 경우
     tmp1 = dp[i - 1][j];
     // i번째 수가 추가되는 경우
     tmp2 = Math.max(dp[i-2][j-1], dp[i-1][j])+ar[i];
     dp[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
    }
   }
  }
  //print();
  System.out.println(dp[N][M]);
 }
 public static void print(){
  for(int i = 1; i <= N; i++){
   for(int j = 1; j <= M; j++){
    System.out.printf("%2d", dp[i][j]);
   }
   System.out.println();
  }
 }
 public static int sum(int from, int to) {
  int sum = 0;
  for (int i = from; i <= to; i++) {
   sum += ar[i];
  }
  return sum;
 }
}

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

문제

문제

출처

ICPC

어디서 틀린걸까요??

hanjh04 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말