[BOJ] 백준 1484번 다이어트 (Java)

#1484 다이어트

난이도 : 골드 4

유형 : 정수론 / 투포인터

1484번: 다이어트

▸ 문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

 

문제 풀이  

투 포인터를 활용하여 문제를 풀이할 수 있다. 최대 100,000의 제곱수를 구해야하기 때문에 long으로 선언해줘야 한다. 다음과 같이 가장 작은 자연수부터 시작해서 두 제곱수의 차가 g가 되는 구간을 기록해준다. 

• dif == g, 해당 구간을 기록한다.
• dif > g, 차이가 크므로 작은 포인터 s를 증가시켜준다.
• dif <=g, 차이가 작으므로 큰 포인터 e를 증가시켜준다.
• flag = false, 만약 찾아낸 구간이 하나도 없으면 -1을 출력한다.

boolean flag = false;
while(e<=100_000) {
	long dif = e*e - s*s;
	if(dif == n) {
		System.out.println(e);
		flag = true;
	}
	
	if(dif >n){
		s++;
	}else {
		e++;
	}
}

 

풀이 코드 

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		long s= 1;
		long e =2;
		
		boolean flag = false;
		while(e<100_000) {
			long ps = s*s;
			long pe = e*e;
			if(pe-ps == n) {
				System.out.println(e);
				flag = true;
			}
			
			if(pe-ps >n){
				s++;
			}else {
				e++;
			}
		}
		
		if(!flag) {
			System.out.println(-1);
		}
	}
}