방과후
ALGORITHM NOTE약 1분

BOJ 1484 - 다이어트

살 좀 빼!!!!!!

#algorithm#boj#gold#two-pointers#math
아카이브로 돌아가기

문제 링크

문제

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

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

입력

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

출력

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

풀이

A^2 - B^2 = G 꼴을 만족하는 자연수 쌍 (A, B)를 찾으면 된다. A는 현재 몸무게, B는 예전 몸무게다.

코드에서는 두 포인터처럼 A, B를 둘 다 1에서 시작한다. 제곱 차가 G보다 작으면 A를 키우고, 크면 B를 키운다. 정확히 같으면 A를 답에 추가한다.

차이가 너무 커져서 A - B == 1인데도 G보다 큰 순간이 오면 더 이상 해가 없으므로 종료할 수 있다.

코드

java
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
 
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());
        System.out.println(solve(G));
    }
 
    static String solve(int G) {
        ArrayList<Long> result = new ArrayList<>();
 
        long A = 1, B = 1;
        while (true) {
            if (A * A - B * B == G) result.add(A);
 
            if (A * A - B * B > G) {
                if (A - B == 1) break;
                else B++;
            }
            else A++;
        }
 
        if (result.isEmpty()) return "-1";
        else return result.stream()
                .map(String::valueOf)
                .collect(Collectors.joining("\n"));
    }
}

복잡도

  • 시간 복잡도: 두 포인터가 가능한 몸무게 범위를 증가시키며 움직이므로 O(G)O(G)이다.
  • 공간 복잡도: 가능한 정답을 저장하므로 정답 개수를 RR이라 할 때 O(R)O(R)이다.

마무리

식은 수학적이지만, 실제 풀이는 아주 정직한 두 포인터다. 제곱 차이가 작으면 키우고, 크면 줄이는 흐름만 유지하면 된다.