2003

수열의 합2 : https://www.acmicpc.net/problem/2003

 

숏코드 : https://www.acmicpc.net/source/42813717

 

 two point 알고리즘도 완탐에 속하나 보다... lt,rt 가지고 전부 순회하긴 하니까

비슷한 문제 전에도 풀어본 기억이 있는데,

이런 문제의 경우 조건문 및 인덱스 범위를 생각해내는게 생각보다 쉽지 않다.

어거지로 껴 맞춰서 일단 Ver1을 만들었으나 찝찝해서 숏코드를 보고 Ver2.를 만들었다.

숏코드와 while 조건문에서의 차이를 발견.. (왜 내거보다 경우의 수를 1개 덜 비교하는지 이해가 안되서 계속 보던 중)

if() else  구조가 아님을 알게되었다. ( 둘중 뭐가 더 좋은지는 본인이 판단하면 되겠지만 실수가 나오면 생각보다 찾기 힘들다)

아마도 sum > m 인경우와 sum < m 인 경우가 동시에 처리되는 경우가 있으며 루프 조건이 하나 적어도 AC 되는 것으로 보인다.

 

하지만 숏코드가 실패하는 반례를 발견했고, 아래의 case에서 오류가 있음이 나타났다.

실제 AC 되지만 아래의 수식에서 오답을 출력한다. 3까지 탐색이 되지만 sum==m 인 경우를 수행하지 않는다.

 

 

 

ex)

5 3
1 3 1 1 3
1

 

정답 : 2 

==========

 

첫번째 예제로 주어지는 아래의 경우를 따져보면...

배열을 1 부터 탐색할 경우,

 

마지막의 rt 값은 5가 되며 cnt를 3으로 만든다. 그러나 rt <= N 조건이라면 이를 카운트 하지 못하고 종료하게 되므로 

rt <= N+1이 되어야 한다.

 

ex) 

4 2

1 1 1 1

 

별것 아닌것 같지만 이런 부분에서 실수가 나오면 시간 가장많이 뺏기는것 같다.

 

Ver. 1

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

public class Main {

	static int N, M;
	static int[] arr;
	static int answer;
	private static boolean DBG = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; ++i)
			arr[i] = Integer.parseInt(st.nextToken());

		int rt = 0, lt = 0;
		int sum = arr[lt];

		while (lt <= rt) {

			if (sum == M) {
				answer++;
				if (DBG)
					System.out.printf("[%d %d]: %d\n", lt, rt, answer);
				if (rt + 1 >= N)// 다음인덱스가 없으므로 이후 같아질 경우는 없다 따라서 종료.
					break;

				sum -= arr[lt++];
				sum += arr[++rt];

			} else if (sum < M) {

				if (rt + 1 == N)// rt를 늘리며 계속 더해준다. N에 도달하면 종료.
					break;
				sum += arr[++rt];
				if (DBG)
					System.out.printf("r[%d %d]: %d\n", lt, rt, sum);
			} else { // sum > M rt==lt인 경우?

				if (lt == rt) {
					if (rt + 1 >= N)// 다음인덱스가 없으므로 이후 같아질 경우는 없다 따라서 종료.
						break;

					sum -= arr[lt++];
					sum += arr[++rt];
				} else {

					sum -= arr[lt++];
				}

				if (DBG)
					System.out.printf("l[%d %d]: %d\n", lt, rt, sum);
			}

		}

		System.out.println(answer);
	}
}

 

 

Ver2. 

 

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

public class Main {

	static int N, M;
	static int[] arr;
	static int answer;
	private static boolean DBG = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; ++i)
			arr[i] = Integer.parseInt(st.nextToken());

		int rt = 0, lt = 0;
		int sum = 0;

		while ( rt <= N) {

			if (sum == M) {
				answer++;
				if (DBG)
					System.out.printf("m[%d %d]: ans %d\n", lt, rt, answer);
				sum -= arr[lt++];
			} else if (sum < M) {
				sum += arr[rt++];
				if (DBG)
					System.out.printf("r[%d %d]: %d\n", lt, rt, sum);
			} else { // sum > M rt==lt인 경우?
				sum -= arr[lt++];
				if (DBG)
					System.out.printf("l[%d %d]: %d\n", lt, rt, sum);
			}

		}

		System.out.println(answer);
	}
}

 

Ver3.

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

public class Main {

	static int N, M;
	static int[] arr;
	static int answer;
	private static boolean DBG = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; ++i)
			arr[i] = Integer.parseInt(st.nextToken());

		int rt = 0, lt = 0;
		int sum = 0;

		while (rt <= N) {
			if (sum > M) { // sum > M rt==lt인 경우?
				sum -= arr[lt++];
				if (DBG)
					System.out.printf("l[%d %d]: %d\n", lt, rt, sum);
			}
			if (sum < M) {
				sum += arr[rt++];
				if (DBG)
					System.out.printf("r[%d %d]: %d\n", lt, rt, sum);
			}
			if (sum == M) {
				answer++;
				if (DBG)
					System.out.printf("m[%d %d]: ans %d\n", lt, rt, answer);
				sum -= arr[lt++];
			}
		}

		System.out.println(answer);
	}
}

 

숏코드 : //https://www.acmicpc.net/source/6546971

//https://www.acmicpc.net/source/6546971
import java.util.Scanner;

public class Main {

	static int n,m,a[]= new int[10001],l,r,su,cnt;

	public static void main(String args[])
	{
		int i;
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();

		for(i=1;i<=n;i++)
		{
			a[i] = sc.nextInt();
		}

		l=r=1;
		while(r<=n) // while(r<=n+1)로 변경하든가 or 인덱스를 0부터 시작하도록 바꾸거나...
		{
			if(su<m)
				su+=a[r++];
			if(su>m)
				su-=a[l++];
			if(su==m)
			{
				cnt++;su-=a[l++];
			}
		}

		System.out.println(cnt);
	}
}