[자바] 백준 1484 - 다이어트 (java)

목차

문제 : boj1484

 

 

필요 알고리즘

• 수학
  
  • 수학 문제긴한데 딱히 수학적 지식이나 알고리즘 지식이 필요한 문제는 아니다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  내 풀이 로직은 다음과 같다. 보면 알겠지만 딱히 수학이나 알고리즘 지식이 필요한 부분은 없다. 다만 이전과의 차이가 G를 넘어서는 제곱수부터는 무시해도 된다는 직관은 필요하다. 저걸로 인해 시간복잡도가 엄청 줄어든다.

 

1. 제곱수들의 리스트를 만드는데, 바로 직전의 제곱수와 차이가 G를 넘어가는 순간 더이상 찾지 않는다. 차이가 G를 넘어간다면 그 이상의 제곱수는 답이 절대 될 수 없으므로 무시해도 된다.

private List<Integer> init(final int g) {
    List<Integer> sq = new ArrayList<>();
    int bf = 0;
    for (int i = 1; i*i-bf*bf <= g; i++) sq.add(bf = i);
    return sq;
}

 

2. 작은 제곱수부터 차례대로 '1'에서 찾았던 제곱수들을 보면서, 현재 보고 있는 제곱수에 G를 뺀 값이 이전에 이미 살펴봤던 제곱수 중 존재했는지 확인한다. 존재한다면 답으로 출력한다.

Set<Integer> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
int cnt = 0;
for (int cur : square) {
    set.add(cur*cur);
    if (!set.contains(cur*cur-g)) continue;
    sb.append(cur).append('\n');
    cnt++;
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    public static void main(String[] args) throws Exception {new Main().solution();}

    private void solution() throws Exception {
        int g = Integer.parseInt(br.readLine());
        List<Integer> square = init(g);
        
        Set<Integer> set = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for (int cur : square) {
            set.add(cur*cur);
            if (!set.contains(cur*cur-g)) continue;
            sb.append(cur).append('\n');
            cnt++;
        }
        System.out.print(cnt==0?-1:sb);
    }

    private List<Integer> init(final int g) {
        List<Integer> sq = new ArrayList<>();
        int bf = 0;
        for (int i = 1; i*i-bf*bf <= g; i++) sq.add(bf = i);
        return sq;
    }
}