[백준] 22238

코드 1, 성공, 230816

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;


public class Main {

    static int gcd(int x, int y){
        int big = x > y? x:y;
        int small = x > y? y:x;

        while(true){
            if(big % small == 0){
                return small;
            } else {
                int temp = big;
                big = small;
                small = temp % small;
            }
        }
    }

    static int[] findSlope(int x, int y){
        int num;
        if (x == 0 || y == 0){
            if(x == 0){
                if(y > 0){
                    x = 0;
                    y = 1;
                } else {
                    x = 0;
                    y = -1;
                }
            } else {
                if(x > 0){
                    x = 1;
                    y = 0;
                } else {
                    x = -1;
                    y = 0;
                }
            }
        } else {
            num = gcd(Math.abs(x), Math.abs(y));
            x = x/num;
            y = y/num;
        }
        return new int[]{x, y};
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> ballon = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> gun = new ArrayList<ArrayList<Integer>>();
        int ballonX = 0;
        int ballonY = 0;
        int[] ballonDire ;
        int total = 0;

        String[] str = br.readLine().split(" ");

        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);

        for(int i = 0; i < n; i++){
            String[] empty = br.readLine().split(" ");
            ballonX = Integer.parseInt(empty[0]);
            ballonY = Integer.parseInt(empty[1]);
            ballon.add(Integer.parseInt(empty[2]));
        }

        ballonDire = findSlope(ballonX, ballonY);
        Collections.sort(ballon);

        int start = 0;
        for(int i = 0; i<m; i++){
            String[] empty = br.readLine().split(" ");
            int[] gunSlope = findSlope(Integer.parseInt(empty[0]), Integer.parseInt(empty[1]));
            if(start != n && (ballonDire[0] == gunSlope[0]) &&(ballonDire[1] == gunSlope[1])){

                int end = ballon.size()-1;
                int mid = 0;
                total += Integer.parseInt(empty[2]);

                while(start <= end){
                    mid = (start+end) / 2;
                    if(ballon.get(mid) <= total){
                        start = mid+1;
                    } else {
                        end = mid-1;
                    }
                }
            }
            System.out.println(n-start);
        }
    }
}

기본 로직

n, m 입력받음

for n 입력

• 방향은 한 점만 저장
• 방어력은 모두 저장

for m 입력

• 방향, 공격력 모두 저장

• if 방향 == 풍선 방향, 기울기 같은 경우

  • 이진 탐색

• print 이진 탐색 결과(start)

기울기

x, y 최대 공약수 구해서 각 x, y 수 나누고 y/x로 구함
- 최대 공약수 - 참고 : https://blockdmask.tistory.com/53
두 수 중에 큰 수를 a, 작은 수를 b라 했을 때
a%b == 0이 될 때 까지 작은 수를 a에 나머지를 b에 대입

이진 탐색

start <= end 일 때 까지 반복문 진행

• start에서 mid + 1로 진행하기 때문에 start부터 시작한다 n-start로 갯수 출력
  

해결

최대 공약수 구하는데 시간 초과

• for문 이용해 처음부터 끝까지 찾는 로직 사용했었다

gun이 공격한 모든 경우의 남은 풍선의 갯수를 출력해야된다

• gun의 공격과 풍선 기울기가 같은 경우만 출력을 했었다

공격이 성공한 경우의 변화하는 풍선의 갯수를 list로 보관하며 하나하나 관리하려 하는 것보다 list를 그대로 두고 total로 합산하고 그 때마다 이진 탐색 출발 지점을 갱신하며 진행

점이 절편인 경우 제대로 고려안함

• 처음에는 기울기를 y변화량/x변화량으로 진행했지만 기울기가 무한대인 경우를 핸들링하지 못해 최대공약수로 나눈 x, y 값을 이용해 기울기를 비교했다