[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);
}
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 3687번 : 성냥개비 Gold2(골드2) - JAVA[자바] (1) | 2024.06.07 |
---|---|
[백준] 14676번 : 영우는 사기꾼? Gold3(골드3) - JAVA[자바] (1) | 2024.06.06 |
[백준] 1700번 : 멀티탭 스케줄링 Gold1(골드1) - JAVA[자바] (1) | 2024.06.04 |
[백준] 20926번 : 얼음 미로 Gold 2(골드 2) - JAVA[자바] (0) | 2024.06.03 |
[백준] 12896번 : 스크루지 민호 Gold2(골드2) - JAVA[자바] (0) | 2024.06.02 |