개발 블로그

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

15

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

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());
            }
        }
    }
}