글 읽기 - 안녕하세요 알고리즘 초보자좀 도와주세요

dlcksdnd321 5년 전 0

부족한 실력으로 열심히 풀었는데 틀렸다고합니다..

그런 제 코드에서 고칠점이랑 반례를 찾아주시면 정~~~~~~~~~~말 감사하겠습니다.

새싹 개발자를 도와주세용

import java.util.Scanner;

public class B2343 {

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int N = sc.nextInt();// 레코드 개수
		int B = sc.nextInt();// 블루레이개수
		long[] rec = new long[N];	
		for (int i = 0; i <N; i++) {
			rec[i]=sc.nextLong();
		}
		int max=0;
		for (int i = 0; i <N; i++) {
			max+=rec[i];
		}

		int left=0; //바이너리 서치의 필수요소  값의 왼쪽
		int right=max;// 값의 오른쪽 
		while(left<=right) {
			int mid = (right+left)/2; //바이너리서치에서 미드 또한 필수
			int count=0;
			long sum=0;
			for (int j = 0; j < N; j++) {
				sum=sum+rec[j];
				if(sum>=mid) {
					sum=0;
					count++;
				}
				else if(j==N-1&&sum<mid) {
					count++;
				}
			}
			
			if(count<=B) { 
				right= mid-1;
			}
			else {
				left=mid+1;
			}
		}
		System.out.println(left);
		long sum2=0;
		long save=0;
		for (int j = 0; j < N; j++) {
			sum2=sum2+rec[j];
			if(sum2>=left) {
				if(save<sum2)
					save=sum2;
				sum2=0;
			}
		}

		System.out.println(save);
	}
}	

djm03178 5년 전 1

왜 출력이 두 군데인가요? 출력해야 할 건 1개입니다.

dlcksdnd321 5년 전 0

답변감사합니다 저기 left 출력줄은 값확인하려고 시험삼아 적어본건데 잘못올렸네요

저기줄 삭제하고 했을때 왜 틀렸는지 잘모르겠습니다 ㅠㅠ

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int N = sc.nextInt();// 레코드 개수
		int B = sc.nextInt();// 블루레이개수
		long[] rec = new long[N];	
		for (int i = 0; i <N; i++) {
			rec[i]=sc.nextLong();
		}
		long max=0;
		for (int i = 0; i <N; i++) {
			max+=rec[i];
		}

		long left=0; //바이너리 서치의 필수요소  값의 왼쪽
		long right=max;// 값의 오른쪽 
		while(left<=right) {
			long mid = (right+left)/2; //바이너리서치에서 미드 또한 필수
			int count=0;
			long sum=0;
			for (int j = 0; j < N; j++) {
				sum=sum+rec[j];
				if(sum>=mid) {
					sum=0;
					count++;
				}
				else if(j==N-1&&sum<mid) {
					count++;
				}
			}
			
			if(count<=B) { 
				right= mid-1;
			}
			else {
				left=mid+1;
			}
		}

		long sum2=0;
		long save=0;
		for (int j = 0; j < N; j++) {
			sum2=sum2+rec[j];
			if(sum2>=left) {
				if(save<sum2)
					save=sum2;
				sum2=0;
			}
		}

		System.out.println(save);
	}
}	

djm03178 5년 전 4

반례 몇 개 드립니다.

5 2
2 5 5 3 3
output: 12
correct answer: 11

5 4
5 5 2 5 1
output: 7
correct answer: 6

4 2
5 1 2 5
output: 8
correct answer: 7

dlcksdnd321 5년 전 0

감사합니다 djm03178님 반례찾아주시는 프로그램이 따로 있는건지.. 정말 신기합니다!!

근데 제 부족한 실력에 어떻게 바꿔야할지 도무지 감이 안오네요 ㅠㅠ

힌트를 조금만더 얻을수 있을까요 ??

djm03178 5년 전 3

정답 솔루션과 오답 솔루션을 놓고, 랜덤으로 반례를 만들어 돌리고 결과를 비교해주는 프로그램을 만들었습니다. 물론, 데이터를 생성해내는 알고리즘은 문제마다 따로 짜야 됩니다.

25번째 줄에서 일단 더해놓고 그 값이 mid 이상이 되면 다시 0부터 시작하는데, 이렇게 하면 너무 늦지 않을까요? 한계선을 넘어버린다는 건 아예 넣지 않고 다음 블루레이로 넘겨야 하는 건데, 넘겼다는 정보가 남아있지 않게 되니까요.

dlcksdnd321 5년 전 0

djm03178님 도움주셔서 정말감사합니다!!!

0부터 시작말고 if 문을 좀수정하고

한계선을 넘은다음에 계산했던 블루레이를 넘기전으로 수정하니까 해결됬습니다

친절히 도움주셔서 감사합니다 정말~~~ 어디물어볼데가 마땅치 않았는데 감사합니당

dlcksdnd321 5년 전 0

한가지만 더부탁하자면 아래 소스 반례 찾는걸좀 부탁드려도 될까요 ??

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int N = sc.nextInt();// 레코드 개수
		int B = sc.nextInt();// 블루레이개수
		long[] rec = new long[N];	
		long max2=0;
		for (int i = 0; i <N; i++) {
			rec[i]=sc.nextLong();
			if(max2<rec[i])
				max2=rec[i];
		}
		long max=0;
		for (int i = 0; i <N; i++) {
			max+=rec[i];
		}
		long left=0; //바이너리 서치의 필수요소  값의 왼쪽
		long right=max;// 값의 오른쪽
		long ans=0;
		while(left<=right) {
			long mid = (right+left)/2; //바이너리서치에서 미드 또한 필수
			int count=1;
			long sum=0;
			for (int j = 0; j < N; j++) {
				if(sum+rec[j]>mid) {
					sum=rec[j];
					count++;
				}
				else
					sum+=rec[j];
			}
			
			if(count<=B) { 
				right= mid-1;
			}
			else {
				left=mid+1;
			}
		}

		System.out.println(left);
	}
}	

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

문제

문제

출처

ICPC

안녕하세요 알고리즘 초보자좀 도와주세요

dlcksdnd321 5년 전 0

djm03178 5년 전 1

dlcksdnd321 5년 전 0

djm03178 5년 전 4

dlcksdnd321 5년 전 0

djm03178 5년 전 3

dlcksdnd321 5년 전 0

dlcksdnd321 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말