글 읽기 - 11052 붕어빵 최대수익 문제 질문합니다.

chucky3 8년 전 0

문제에 제시되어 있는 예제는 전부 맞구요..

여러번 테스트해봤는데 오류없이 잘되는데 어떠한 예외가 있을까요?

import java.util.Scanner;

public class Main{
	public static void main(String arg[]){
		Scanner input = new Scanner(System.in);
		int n=input.nextInt();
		int price[]=new int[n];
		for(int i=0;i<n;i++)
			price[i]=input.nextInt();
		System.out.println(set(n,price));
			
	}
	public static int set(int n,int price[]){
		int sum,max=0,cur;
		for(int i=n;i>0;i--){
			sum=0;
			cur=n;
			for(int j=i;j>0;j--){
				if(cur-j==0){
					sum+=price[n-(n-j+1)];
					cur-=j;
					break;
				}else if(cur-j>0){
					sum+=price[n-(n-j+1)];
					if((cur-j)>=j){
						cur-=j;
						j++;
					}else{
						cur-=j;
					}
				}
				
			}
			if(sum>max)
				max=sum;
		}
		return max;
	}
}

yohan5050 8년 전 0

음 코드가 너무 이해하기 어렵네요. 조금이라도 변수나, 알고리즘을 설명해주시면 답변하기 좋을 것 같습니다.

그래서 제 추측이 정확하지는 않겠지만, 일단 질문하신 분의 알고리즘은

모든 경우를 다 검토하지 못하는 것 같아요

예를들어 n이 10인 경우

10개 set

9set + 1set

8 2

7 3

6 4

5 5

4 4 2

3 3 3 1

2 2 2 2 2

1 1 1 1 1 1 1 1 1 1

이정도 경우만 살펴보게 되는 것 같은데요,

만약 3set + 3set + 4set이 최대 가격을 가질 경우, 이 예시를 살펴보지 않으니 틀리겠죠?

제가 예시를 실행해봤는데요,

1 2 8 10 11 12 13 14 15 16

이 경우 3set+ 3set + 4set해서 26이 최대값인데, 질문자님의 코드를 이용할 경우

3set+3set+3set+1set으로 계산해서 25가 나오는 것 같습니다.

chucky3 8년 전 0

감사합니다~알아내긴했는데 알고도 짜는게 참쉽지않네요ㅎㅎ도움됬습니다

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

문제

문제

출처

ICPC

11052 붕어빵 최대수익 문제 질문합니다.

chucky3 8년 전 0

yohan5050 8년 전 0

chucky3 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말