백준 2559번: 수열 with Java

수열

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

60632

22534

17413

36.032%

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

 

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

 

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

예제 입력 1 복사

10 2
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 1 복사

21

예제 입력 2 복사

10 5
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 2 복사

31

 

 

---

 

 

ㅎ ㅏ... 어제 하고 잘라 했는데

알바 + 치맥의 효과인가? 잠깐만 누워있겠다는 게 그만 잠을 쳐자고 말았따. 이대로라면 치과에서 충치 10개가 나올지도 모른다. 그 와중에 자다가 더워서 그런가 오지게 깼는데 어 해야 하는데!.... 하다가 커어어어어어 다시 잠. 할 게 많은데~ 왜 잠을 자고 그러니~

30분 안에 뭔가 틀을 만들 수 있을까?... 나머지는 알바 가서 시루할란다...  -> 결국 안 하고 집 와서 하는 중 ㅎ

 

 

또 수열 문제다...^^

며칠간 온도의 합이 가장 큰 지는 왜 궁금한데...?...

 

max 잡아놓고 계속 더해보고 max 출력하면... 또 시간 폭발할라나?

일단... 해보자

-> 못함. 생각해보니까 2 2 2 2 2 2 이런 식으로 더해서 젤 큰 거 나오면...

 

그러면 양수만 더해야지 젤 큰 거 잖아 음수 나오면 탈출한 담에 그 담 꺼 더해보기...??

 

입력: n(전체 날짜 수 2 <= n <= 100000) k(연속 날짜????? 1 <= k <= n)

n개의 정수....

 

k를 주는 거였구나... 연속 날짜를... 주는 거였어....

전혀 몰랐네

 

그러면 짜볼게요....

 

그렇게 나온 1차 코드...

import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int[] weathers = new int[n];
		for (int i = 0; i < n; i++) {
			weathers[i] = sc.nextInt();
		}
		
		int max = 0;
		for (int i = 0; i < n - k; i++) {
			int tmp = 0;
			for (int j = i; j < i + k; j++) {
				tmp += weathers[j];
			}
			if (tmp > max) {
				max = tmp;
			}
		}
		
		System.out.println(max);
		
		sc.close();
	}
}

 

딱 봐도 생각을 하지 않았다.

 

그러니 역시나

전혀 놀랍지 않은 결과

 

 

그런데 코드를 고치려고 하는데 놀랍게도 어디를 고쳐야 하는지 모르겠다 

심지어 테스트 케이스 두 개 공개된 게 다 돌아간다 이게 더 놀라움;;; 이게 돌아간다고?

 

그래서 뭐가 문제라서 틀린건데...

 

계속 생각하는데

내게 남은 시간 20분

오 생각해보니까 전부 마이너스일 수도 있네... 그러면 max를 바꿔볼까

 

신나게 MIN_VALUE 사용 찾아옴

 

그리하여 두 번째 코드

 

import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int[] weathers = new int[n];
		for (int i = 0; i < n; i++) {
			weathers[i] = sc.nextInt();
		}
		
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n - k; i++) {
			int tmp = 0;
			for (int j = i; j < i + k; j++) {
				tmp += weathers[j];
			}
			if (tmp > max) {
				max = tmp;
			}
		}
		
		System.out.println(max);
		
		sc.close();
	}
}

 

 

또 틀림...

 

 

즉석에서 대충 짜낸 코드에 자신감이 상승해서 이제 왜 안 돌아가냐고 화내는 중

왜 안 되는 건데 그래서

 

 

바보인가? 반복문에서 k 뺀 다음에 1을 안 더해줬다

바보 인증...?

import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();	// 측정한 날짜 수
		int k = sc.nextInt();	// 연속 날짜 개수
		
		int[] weathers = new int[n];	// 온도 저장 배열
		for (int i = 0; i < n; i++) {
			weathers[i] = sc.nextInt();
		}
		
		int max = Integer.MIN_VALUE;	// 최대값은 integer의 최소값으로 받는다 마이너스 나올 수도 있으므로 0 안 됨
		// n - k + 1 까지 돌게 만들어서 맨 끝까지 더할 수 있게 해줌
		for (int i = 0; i < n - k + 1; i++) {
			int tmp = 0;	// 온도 합 더할 변수
			for (int j = i; j < i + k; j++) {
				tmp += weathers[j];	// k개 온도 더함
			}
			if (tmp > max) {
				max = tmp;
			}	// k개 온도 합이 max보다 크면 tmp를 max에 넣어줌
		}
		
		System.out.println(max);
		
		sc.close();
	}
}

 

 

 

와!!!!!!! 돈다 돌아!!!!!!!!!!!!

오늘은 더 심각한 메모리와 시간

아.... 시간을 안 보는 문제라 다행이야 그랫으면 난 댕강!!!!

이건

정말

해결이 필요하다...

근데 지금은 너무 피곤해서 낼 볼게요 전 돌아가는 거에 만족하겠습니다.