[Java] 백준 1484번 - 다이어트 (완전 탐색)

문제 링크 : https://www.acmicpc.net/problem/1484

1484번: 다이어트

 

문제

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

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

입력

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

출력

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

예제 입력 1 

15

예제 출력 1 

4
8

 

---

접근 방법

이 문제는 보통 투포인터로 많이 푸는 문제이다. 즉, G = (현재+기억)*(현재-기억) 인 점을 활용하여 현재 몸무게와 기억하는 몸무게 간의 관계를 바탕으로 정해진 범위 내에서 몸무게 2개를 조절해가면서(투포인터) 수식을 만족하는 현재 몸무게를 찾는 방식이다. 

 

나는 G = (현재+기억)*(현재-기억) 에서 

• a = 현재+기억
• b = 현재-기억

a+b  = 2*(현재) 이므로 a+b는 짝수

인 점을 활용했다. 

 

탐색 범위는 a가 1부터(현재, 기억 모두 자연수이므로 2부터 해도 됨) G까지 했다.

G까지 한 이유는 다음과 같다.

현재와 기억의 최소 차이를 생각해봤을 때 b = 현재-기억 은 양수이므로 현재와 기억 몸무게의 최소 차이는 1이다. 이 경우를 조건의 끝이라고 생각하면 G = a가 된다. 

 

추가로

1) b = G/a인 점

2) a와 b 모두 양수인 점(a와 b를 곱해서 G가 나와야하며 G는 자연수이므로)

3) 현재 몸무게가 자연수이고, 기억하는 몸무게도 자연수인 점(13번째 line에서 a<=b가 아닌 a<b로 하면 오답으로 나온다. 즉 a>=b인 경우를 고려하면 틀린다는 소리이며 그 중 a=b인 경우가 오답의 원인이 되는 것이다. 아래 링크도 추가 참고하면 기억하는 몸무게도 자연수로 고려해야하는 것 같다.)

 

https://www.acmicpc.net/board/view/115572

글 읽기 - 문제 내용 추가 요청입니다.

 

 

아래 반례가 도움이 되었다. 

https://www.acmicpc.net/board/view/99783

글 읽기 - 1484. 다이어트 질문입니다.

import java.util.*;

public class BOJ_1484_다이어트 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        TreeSet<Integer> set = new TreeSet<Integer>();

        int G = sc.nextInt();
        for(int a = 1; a<=G; a++){	//a 탐색 범위를 1부터 G까지 해야함.
            if(G%a != 0) continue;		//b가 G의 약수가 아니면 패스
            int b = G / a;				//b는 G의 약수 
            if(((a+b) % 2 != 0) || (a<=b)) continue;	//짝수가 아니거나 범위 벗어나면 패스
            set.add((a+b)/2);
        }
        if(set.size() == 0){
            System.out.println(-1);
        }

        else{
            Iterator iter = set.iterator();
            while(iter.hasNext()){
                System.out.println(iter.next());
            }
        }
    }
}