/ SWEA

SWEA_12742_장마속의막대_JAVA

문제 : 장마속의막대

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_12742_장마속의막대

접근 방식

방정식 풀이 하듯 풀어보자.

막대가 쭉 늘어서 있고 장마로 인해서 물이 잠겨서 수면 위에 드러난 부분이 a와 b이다.

그러면 a가 x번째, b가 x+1번째 막대라고 한다면

b-a는 1부터 (x+1)까지의 합 - 1부터 x까지의 합이다.

위 식을 계산하면 결국 x+x+1 - x. 즉, x+1 = b-a가 되고, x는 b-a-1이 된다.

그렇다면 K는 어떻게 구할까?

막대의 길이는 1~x까지의 합이다.

물이 잠겨서 수면위에 드러난 부분이 a라고 생각하다. 전체 길이인 1~x까지의 합에서 K를 빼면 a가 나온다.

1~x까지의 합 - K = a이고,

1~x까지의 합 - a = K이다.

위 식을 정리하면

x = b-a-1 에서 x를 구하고

K = 1~x까지의 합 - a 에서 K를 구하면 된다.

풀이 방법

  1. 값을 읽어와서 각각 A, B에 저장한다.

  2. X를 선언하고 A-B-1을 저장한다.

  3. 3-1. 1~X까지 반복한다. X까지의 합을 구한다.

  4. 3-2 등차수열의 합 공식 (X*X+1)/23 이용한다.

  5. 1~X까지의 합에서 A만큼 뺀다.

  6. 결과를 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

/*
 * 방정식 풀이 하듯 풀어보자.
 * 막대가 쭉 늘어서 있고 장마로 인해서 물이 잠겨서 수면 위에 드러난 부분이 a와 b이다.
 * 그러면 a가 x번째, b가 x+1번째 막대라고 한다면
 * b-a는 1부터 (x+1)까지의 합 - 1부터 x까지의 합이다.
 * 위 식을 계산하면 결국 x+x+1 - x. 즉, x+1 = b-a가 되고, x는  b-a-1이 된다.
 * 그렇다면 K는 어떻게 구할까?
 * 막대의 길이는 1~x까지의 합이다.
 * 물이 잠겨서 수면위에 드러난 부분이 a라고 생각하다. 전체 길이인 1~x까지의 합에서 K를 빼면 a가 나온다.
 * 1~x까지의 합 - K = a이고,
 * 1~x까지의 합 - a = K이다.
 * 위 식을 정리하면
 * x = b-a-1 에서 x를 구하고,
 * K = 1~x까지의 합  - a 에서 K를 구하면 된다.
 */
public class IM_12742_장마속의막대 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("input_12742.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for(int tc=1;tc<=T;tc++) {
			String[] str = in.readLine().split(" ");
			int A = Integer.parseInt(str[0]);
			int B = Integer.parseInt(str[1]);
			int X = B-A-1;
			int answer = 0;
//			for(int i=1;i<=X;i++) {
//				answer += i;
//			}
//			answer = answer - A;
			answer = (X*(X+1))/2 - A;

			// -- 출력부
			System.out.printf("#%d %d\n",tc,answer);
		}
	}
}