📙[Algo] 24.01.19 알고리즘

알고리즘 문제) BOJ1484. 다이어트 

1484번: 다이어트

문제 요약

• G킬로그램 : 현재 몸무게의 제곱 - 기억하고 있던 몸무게의 제곱
• 현재 몸무게로 가능한 것을 모두 출력
• 현재 몸무게는 기억하고 있던 몸무게보다 크다.

시간 제한

• 2초

입력

• G ( 10만 이하의 자연수)

출력

• 가능한 몸무게를 오름차순으로 출력.
• 없다면 -1 출력
• 만약 자연수로 떨어지지 않는 경우는 제외

접근법

먼저 완전 탐색으로 접근하기
현재 몸무게 : X
기억하고 있던 몸무게 : Y
G = X*X - Y*Y = (X+Y)(X-Y)
2중 for문을 돌려서 “XX - YY = G ( X > Y)”인 경우를 찾아 출력한다.
⇒ 하지만 10만*10만으로 무조건 시간 초과! 그리고 가능한 X, Y범위를 제한하면 안 됨.

 

최적화 하기
모든 수치를 다 계산하면 안 된다. 또한 범위 제한을 하면 안되므로 while문을 사용해야한다.

곱했을 때 int타입을 넘어갈 수 있으므로 long타입에 x, y변수를 담고 시작한다. 
x=2, y=1

• 4 - 1 = 3 < G
• x기준 가장 작은 숫자 y와 계산한 것이므로, y를 늘려봤자 의미 없다. x+=1

x=3, y=1

• 9 - 1= 8 < G
• x기준 가장 작은 숫자 y와 계산한 것이므로, y를 늘려봤자 의미 없다. x+=1

x=4, y=1

• 16 - 1 = 15 == G
• 답이므로 출력
• 답을 찾음. 여기서 x기준 가장 작은 숫자 y와 계산한 것이므로, y를 늘려봤자 의미 없다.
• x+=1

x=5, y=1

• 25 - 1 = 24 > G
• 여기서 x기준 가장 작은 숫자 y와 계산한 것이므로, x와 y사이에 잠재적 후보들이 존재(차이를 줄여야 하니까).
• y+=1

이렇게 진행한다.
언제까지? X기준 가장 큰 Y랑 계산해도 G보다 큰 경우 더 이상 탐색할 필요가 없다.
그렇게 되면 y가 자동으로 +1 되고, 이때 x와 y가 같아지면서 탐색을 종료한다. 

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int G = Integer.parseInt(br.readLine());

        long x = 2, y = 1;
        while (true) {

            if(x == y) break;

            if(x*x - y*y < G) x++;
            else if(x*x - y*y > G){ y++;}
            else{
                sb.append(x+"\n");
                x++;
            }

        }

        if(sb.isEmpty()) sb.append(-1);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}