| Scanner 와 BufferedReader의 차이

이번 글은 자바를 처음 배울때 한번쯤은 써봤을 법한 클래스인 Scanner와 프로그래밍에 조금 더 익숙해지거나 특히 알고리즘 문제를 풀다가 자주 접하게 될 BufferedReader 클래스의 차이에 대해 알아보겠습니다.

결론부터 말하자면 가장 큰 차이점은 속도!!

 

package milk;

import java.util.Scanner;

public class study {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.println("원하는 숫자를 입력하세요");
		String input = scanner.nextLine();
		int num = Integer.parseInt(input);

		System.out.println(num);
	}

}

 

우리는 보통 자바를 처음 배울때 콘솔에서 입력을 받기 위해 이러한 방식을 많이 사용했을 것이다. 하지만 Scanner는 편리하지만 속도가 느리다는 단점이 있어 특히 알고리즘 문제를 풀때 시간초과 에러를 내는 치명적인 단점이 있습니다. 하하지만  BufferedReader 를 아래와 같이 사용한다면 버퍼를 사용하기 때문에 입력 속도에서 확연히 줄일 수 있습니다.

package milk;

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

public class study {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
		String s = br.readLine(); 
		int i = Integer.parseInt(br.readLine()); 
		
		System.out.println("String : " + s);
		System.out.println("Int : " + i);
		
	}
}

 

 

 

각 언어마다 입력방식에 대한 속도가 차이가 조금씩 있습니다. 알고리즘 사이트에서 보면 C/C++이 JAVA 보다 실행속도가 빠른 이유가 여기에 있습니다.

입력방식에 따른 속도 차이






개발자라면 한번쯤 사용해 봤을 이클립스, 쓰다보면 기본 클래식 테마에 지루함을 느껴본 적이 있을 것 같아요.          오랜시간 보는 화면인 만큼 환경이 중요하겠죠..! 저도 하얀 화면을 오래보고 눈이 아프다보니 검은 화면을 더 선호하게 되었습니다.

그럼 어두운 화면으로 바꾸어 보겠습니다.

 

1. 메뉴바에 있는 [Window] - [Preferences]를 클릭합니다.

 

2. [General] - [Appearance] - [Theme]를 보면 원하는 취향에 맞게 선택할 수 있는 테마 종류들이 나타납니다.

원하는 테마 선택후 [Apply and Cloase] 클릭!

 

3. 기존 하얀 배경이었던 테마가 검정으로 바뀌었습니다.

 

이클립스에서 기본으로 제공되는 것 외 다른 테마도 사용하는 법!

 

1. [Help] - [Eclipse Marketplace...] 클릭

 

2. theme 를 검색하면 [Darkest Dark Theme with DevStyle CI] 라는 이름의 테마 [install] 클릭!

 

 

3. [confirm] 클릭

4. [Finish] 완료버튼 클릭!

 

5. 아래 빨간 네모 install 문구를 더블클릭하면 진행상황을 볼 수 있습니다.

 

6. [RESTART NOW] 클릭

 

7. 아까와는 다른 스타일의 어두운 테마로 변경 완료!

자바 프로그램 실행과정

- Java언어로 프로그래밍된 파일을 Java컴파일러가 가상 기계어 파일인 Java클래스 파일로 만든다. 다시 말해, 소스 코드를 Java바이트 코드로 번역한다. 이후 Java바이트 코드를 JVM이 읽고 실행하게 된다.

1.1. 바이트 코드란?

- JVM이 이해할 수 있는 언어로 변환된 자바 소스 코드를 의미한다. 자바 컴파일러에 의해 변환되는 코드의 명령어 크기가 1바이트라서 자바 바이트 코드라고 불린다. 이러한 자바 바이트 코드의 확장자는. class이며 자바 바이트 코드는 자바 가상 머신만 설치되어 있으면, 어떤 운영체제에서 라도 실행될 수 있다.

1.2. JVM이란?

- JVM은 JavaVirtual Machine의 줄임말로 wirte once, run erveywhere 즉 OS마다 따로 코드를 작성해야 하는 번거로움 업이 Java가 플랫폼에 독립적일 수 있게 만들어준다. 예를 들어 C 프로그램은 바로 기계어로 컴파일하므로 HW 기종에 맞게 컴파일되어야 한다. 이를 '플랫폼에 종속적'이다. 라고 한다. 반면 Java 프로그램은 중간 단계 언어로 컴파일하여 JVM만 각 OS만 설치되어 있다면 HW 기종에 상관없이 단 한 번만 컴파일하면 된다. 이를 '플랫폼에 독립적'이라고 한다. 간단히 말해 JVM은 Java 클래스 파일을 로드하고 바이트 코드를 해석하며, 메모리 등의 자원을 할당하고 관리하며 정보를 처리하는 작업을 하는 프로그램이다.

 

  • JRE는 자바 API와 JVM으로 구성되며, JVM의 역할은 자바 애플리케이션을 클래스 로더를 통해 읽어 들여서 자바 API와 함께 실행하는 것임.
  • 자바 프로그램을 컴파일하면, JVM은 클래스 로더를 이용해서 컴파일된 바이트 코드를 메모리로 읽어들인다.
    class Loader에 의해 바이트코드가 런타임 데이터 영역(Runtime Data Area)에 올라가게 되면 
    실행 엔진(Execution Engine)이 바이트코드를 한줄씩 실행시킨다. 이 과정 속에서 JVM은 필요에 따라 garbage collection 등의 작업을 수행하게 된다.
  • JVM의 메모리 구조는 활용 용도에 따라 여러 영역으로 구분되어 있는데, 메소드, 스택, 힙 영역이 프로그래밍과 관련이 있다.
  • 지정된 클래스에서 main(String[] args)를 호출한다. 
  • Java Compilerava Source파일을 JVM이 해석할 수 있는 Java Byte Code(. class)로 변경한다. 일반적인 윈도우 프로그램의 경우, Compile 이후 Assembly 언어로 구성된 파일이 생성된다.
  • Class LoaderJVM내로. class파일들을 Load 한다. Loading 된 클래스들을 Runtime Data Area에 배치된다. 일반적인 윈도우 프로그램의 경우 Load 과정은 OS가 주도한다.
  • Execution Engine은 Loading 된 클래스의 Bytecode를 해석한다. 이 과정에서 ByteCode가 BinaryCode로 변경된다. 일반적인 윈도우 프로그램의 경우 Assembier가 Assembly언어로 쓰인 코드 파일을 BinaryCode로 변경한다.
  • Runtime Data AreaJVM이 프로세스로써 수행되기 위해 OS로부터 할당받는 메모리 영역이다. 저장 목적에 따라 다음과 같이 5개로 나눌 수 있다.

 

  - Method Area
모든 Thread에게 공유된다. 클래스 정보, 변수 정보, Method정보, static변수 정보, 상수 정보 등이 저장되는 영역
  - Heap Area
모든 Thread에게 공유된다. new 명령어로 생성된 인스턴스와 객체가 저장되는 구역, 공간이 부족해지면 Garbage Collection이 실행된다.
  - Stack Area
각 스레드마다 하나씩 생성된다. Method안에서 사용되는 값들(매개변수, 지역변수, 리턴 값 등)이 저장되는 구역, 메서드가 호출될 때 LIFO로 하나씩 생성되고, 메서드 실행이 완료되면 LIFO로 하나씩 지워진다.
  - PC Register
각 스레드마다 하나씩 생성된다. CPU의 Register와 역할이 비슷하다. 현재 수행 중인 JVM명령의 주소 값이 저장된다.
  - Native Method Stack
각 스레드마다 하나씩 생성된다. 다른 언어(C/C++ 등)의 메서드 호출을 위해 할당되는 구역 언어에 맞게 Stack이 형성되는 구역이다. JNI(Java Native Interface)라는 표준 규약을 제공한다.

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어 졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른 다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

  1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
    1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
    2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
  2. 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.


#include <iostream>
using namespace std;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int cnt=0,x;
 	int stick=128;
 	cin >> x;
 	
 	while(stick>1)
 	{
 		stick/=2;
 		x-=stick;
 		if(x<0)
 			x+=stick;
 		else
 			cnt++;
 	}
 	cout << cnt ;
 }

 

문제

어떤 양의 정수 X의 자릿수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.


#include <iostream>
using namespace std;

int dydwo(int n) // 101
{
	int i, j,count=0,temp;
	for (i = 1; i <= n; i++)
	{
		temp = i / 10 % 10 - i % 10;
		for (j = i/10; j > 9; j /= 10) if (temp != j / 10 % 10 - j % 10) break;
		count += (j <10);
	}
	return count;
}
int main()
{
	int n;
	cin >> n;
	cout << dydwo(n);
}

 

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

힌트

A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

 


조금만 생각해보면 쉽게 해결되는 문제이다.

S = A[0]*B[0] + ... + A[N-1]*B[N-1] 에서

S의 값이 가장 작아지려면 각 배열의 작은값 X 큰값이 만나서 계산되어야 한다.

작은값 X 작은값이 만나면 작은수를 만들수 있기는 하지만 결국 큰 값 X 큰 값이 만나기 때문에

최종 S의 값은 커질수 밖에 없다. 이를 위해 A 배열은 오름차순 , B 배열은 내림차순으로 재배치하여

각각의 배열에 같은 인덱스에 대한 값을 계산한 뒤 S 변수에 누적시켜 출력하였다.

 

using namespace std;

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	vector<int> A;
	vector<int> B;
	int N, input;
	int ans = 0;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> input;
		A.push_back(input);
	}

	for (int i = 0; i < N; i++){
		cin >> input;
		B.push_back(input);
	}

	sort(A.begin(), A.end());
	sort(B.begin(), B.end(),greater<int>());

	for (int i = 0; i < N; i++)
		ans = ans + A[i] * B[i];

	cout << ans;
}

문제

크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.

이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다.

예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.

  1. 출력은 r1행부터 r2행까지 차례대로 출력한다.
  2. 각 원소는 공백으로 구분한다.
  3. 모든 행은 같은 길이를 가져야 한다.
  4. 공백의 길이는 최소로 해야 한다.
  5. 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
  6. 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.

입력

첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다.

출력

r2-r1+1개의 줄에 소용돌이를 예쁘게 출력한다.

 


 

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int xdir[] = { 0,-1,0,1 }, ydir[] = { 1,0,-1,0 }, ptr, sz=1, buf;
string ans[55][55];
int main()
{
    int r1, c1, r2, c2, x = 0, y = 0, cx, cy, sn = 1, mxl = 0;

    cin >> r1 >> c1 >> r2 >> c2;
    cx = -r1, cy = -c1;

    for (int i = 0; i <= 30000; i++)
    {
        if ((r1 <= x && x <= r2) || (c1 <= y && y <= c2))
        {
            int tx = x, ty = y;
            for (int j = 0, k = sn; j <= sz; j++, k++)
            {
                if (r1 <= tx && tx <= r2 && c1 <= ty && ty <= c2)
                {
                    ans[tx + cx][ty + cy] = to_string(k);
                    mxl = max(mxl, (int)to_string(k).length());
                }
                tx += xdir[ptr], ty += ydir[ptr];
            }
        }
        x += sz*xdir[ptr];
        y += sz*ydir[ptr];
        sn += sz;
        buf++;
        if (buf == 2) sz++, buf = 0;
        ptr = (ptr + 1) % 4;
    }
    for (int i = r1 + cx; i <= r2 + cx; i++)
    {
        for (int j = c1 + cy; j <= c2 + cy; j++)
        {
            while (ans[i][j].length() < mxl) ans[i][j] = " " + ans[i][j];
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}

https://www.acmicpc.net/problem/1021

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.


단순하게 접근했다.

양방향 데이터 접근이 가능한 deque를 사용하여

앞 / 뒤 쪽 더 가까운 곳을 확인 후 카운팅하면서 빼내었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.StringTokenizer;

// BOJ_1021번
// 회전하는 큐
public class Main {

	static int N, M;

	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());
		int target;
		int idx=1;
		int cnt =0;
		Deque<Integer> dq = new ArrayDeque<Integer>();

		for (int i = 0; i < N; i++)
			dq.add(i + 1);

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < M; i++) {
			target = Integer.parseInt(st.nextToken());
			idx = 1;
			Iterator<Integer> it = dq.iterator();
			while (it.hasNext()) {
				if (it.next() == target)
					break;
				idx++;
			}
			
			int front = idx - 1;
			int back =  dq.size() +1 -idx;
			
			if(front < back)
			{
				for(int j =0; j<front; j++) {
					dq.addLast(dq.pollFirst());
					cnt++;
				}
				dq.pollFirst();
			}
			else 
			{
				for(int j=0; j<back; j++) {
					dq.addFirst(dq.pollLast());
					cnt++;
				}
				dq.pollFirst();
			}
		}
		System.out.println(cnt);
	}
}

 

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 


전형적인 BFS / DFS 방법으로 풀 수 있는 문제다.

선언된 2차원 배열에서 각 자리에서 DFS가 수행 될 때, 몇 번의 전체 카운트가 되는지만 생각해주면 될 것 이다.

2차원 배열 각자리에서 하나씩 방문여부를 체크하면서 돌렸는데

더 효율적인 방법도 있을 것 같다..

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

// BOJ_1025 유기농 배추

// DFS 몇번의 뭉탱이로 돌아가는지 카운트
public class Main {

	static boolean map[][];
	static boolean visited[][];
	static int dx[] = { 1, 0, -1, 0 };
	static int dy[] = { 0, 1, 0, -1 };
	static int M, N, K, cnt;

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

		int T = Integer.parseInt(st.nextToken());

		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken()); // 가로길이
			N = Integer.parseInt(st.nextToken()); // 세로길이
			K = Integer.parseInt(st.nextToken()); // 배추 심어져 있는 위치 개수

			map = new boolean[N + 1][M + 1];
			visited = new boolean[N + 1][M + 1];

			for (int k = 0; k < K; k++) {
				st = new StringTokenizer(br.readLine());
				int X = Integer.parseInt(st.nextToken());
				int Y = Integer.parseInt(st.nextToken());

				map[Y][X] = true;
			}
			cnt = 0;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] && !visited[i][j]) {
						cnt++;
						visited[i][j] = true;
						DFS(i, j);
					}
				}
			}
			System.out.println(cnt);
		}
	}

	public static void DFS(int y, int x) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (ny < 0 || N < ny || nx < 0 || M < nx)
				continue;

			if (!visited[ny][nx] && map[ny][nx]) {
				visited[ny][nx] = true;
				DFS(ny, nx);
			}
		}
	}
}

문제

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.

김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. ( 0 ≤ x < y < 231)

출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 회수를 출력한다.


 

#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
 
int bruteForce(ll remaining, int speed)
{
    int ret = 0;
    while (remaining > 0)
    {
        if (remaining > speed * 2)
        {
            ret += 2;
            remaining -= speed * 2;
            speed++;
        }
        else
        {
            int quotient = remaining / speed;
            remaining -= quotient * speed;
            ret += quotient;
            speed--;
        }
    }
    return ret;
}
 
int main()
{
    int cases;
    cin >> cases;
    for (int i = 0; i < cases; i++)
    {
        ll x, y;
        cin >> x >> y;
 
        cout << bruteForce(y - x, 1) << endl;
    }
 
    return 0;
}

+ Recent posts