[백준] 1484번 : 다이어트 Gold5(골드5) - JAVA[자바]

[Gold V] 다이어트 - 1484

문제 링크

성능 요약

메모리: 11740 KB, 시간: 72 ms

분류

수학, 두 포인터

제출 일자

2024년 6월 5일 16:51:38

문제 설명

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

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

입력

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

출력

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

 

접근 방법

1. 현재 몸무게를 A, 기억한 몸무게를 B라고 두고 시작한다.

2. A^2 - B^2 = G인 A를 전부 출력해야한다.

3. 이는 ( A + B ) * ( A - B ) = G로 치환이 가능함.

4. A - B는 양수일 수 없으므로 최소값은 1이다.

5. 현재 몸무게가 G일 때 종료 조건이 된다.

 

풀이 코드

import java.io.*;

/**
 * 문제 : BOJ_1484_다이어트_G5
 * 메모리: 11740KB
 * 시간: 72ms
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int G = Integer.parseInt(br.readLine());
        int s = 1; // 기억
        int e = 2; // 현재

        StringBuilder sb = new StringBuilder();
        while (e <= G) {
            // 현재^2 - 기억^2 = G
            // (현재 + 기억)(현재 - 기억) = G
            int result = (e + s) * (e - s);
            if(result == G){
                sb.append(e).append('\n');
            }

            if(result > G){
                s++;
            }else{
                e++;
            }
        }

        if (sb.length() == 0) {
            System.out.println(-1);
        }else{
            System.out.println(sb);
        }
    }
}