[백준]22238: 🔫가희와 btd5 - JAVA

[백준]22238: 가희와 btd5

22238번: 가희와 btd5

풀이

🪑 근 3일동안 풀었던 문제이다. 출력초과와 틀렸습니다와 시간초과와 싸웠다.

알고리즘 유형이라고 한다면, 구현 + 이분탐색 이라고 생각한다. 문제에 있는 함정을 유의하자!

 

📝 문제를 정리해 보자!

• Drating Gun Tower는 0,0에 하나 있다.
• Darting Gun Tower가 공격을 하면 공격 방향에 놓인 모든 풍선들은 동일한 damage의 피해를 입는다.
• Darting Gun Tower가 특정 방향으로 최대 damage의 공격을 했을 때 모든 풍선을 제거할 수 있다

 

 

🙋‍♀️ 나는 마지막 조건인 '특정 방향으로 최대 damage의 공격을 했을 때 모든 풍선을 제거할 수 있다' 라는 말이 하나의 예외 케이스 인줄 알았다.

• 그래서 어느 한 방향으로 10^9 이상의 공격을 하면 모든 풍선을 제거한다는 예외 케이스를 줘야하는 줄 알았다.
• 이렇게 풀다보니 계속 틀렸었다.
• 한 이틀째쯤 되던 날이 되서야 해당 조건의 의미를 알 수 있었다.
• 해당 조건의 의미는 입력으로 주어지는 풍선들이 모두 한 방향에만 존재한다는 말이었다. 예제 입력에서도 알 수 있듯이 모든 풍선은 한 방향에만 존재하고 있다.
• 그러므로 문제를 풀 때에도 매번 풍선의 방향을 저장해 줄 필요가 없어졌다!

 

 

🔧 문제를 풀어 보자!

1. 풍선의 정보를 입력 받는다. 
2. 타워의 정보를 입력 받는다.
3. 타워가 입력될 때마다 풍선에 공격을 한다.

 

🔹 풍선의 정보를 입력 받는다. 

• 풍선은 모두 한 방향에 위치하므로 매번 방향을 계산해 줄 필요는 없다. 마지막으로 입력된 풍선의 방향만 한 번 계산해 주도록 할 것이다.
• 풍선들의 체력 정보를 ArrayList에 담아 주었다.

 

 

🔹 입력된 좌표를 가지로 방향으로 변환해 주자! 

• Darting Gun Tower는 항상 0, 0에 위치하므로 다양한 방법으로 구할 수 있다.
• 처음에는 기울기를 사용하여 x좌표를 y좌표로 나눠 주었다. 이렇게 하면 결과 값이 부동 소수점으로 표현 되기 때문에 정확한 연산이 불가능 하다는 점이 있다. 오차가 매우 적은 연산의 경우 엄연히 다른 기울기를 가지지만 같은 기울기를 가진다고 계산되는 예외 상황이 발생할 수 있다.
• 그 다음에는 각도를 사용하여 방향을 판별하도록 하였다. 그러나 처음에 생각한 방법과 마찬가지로 여전히 계산에 오차가 존재했다.
• 그 다음으로는 BigDecimal을 사용했다. 단순히 오차를 없애고 정확한 연산을 하기 위해 사용하려 했지만 BigDecimal은 소수점 이하 몇번째 자리까지 표현해 줄 것인지 지정을 해 주어야 했고 이를 판단하기가 어려웠다.
• 마지막으로 생각한 방법이 약수를 사용한 방법이다. x와 y의 최대 공약수를 찾아 그 수로 x와 y를 나눈 값이 타워에서도 마찬가지로 약수를 구해 나눈 값과 같다면 같은 방향을 바라보고 있다고 판단할 수 있으며 직접 나눠주는 연산이 필요 없기 때문에 오차가 발생할 일도 없다.
• 다만 위방법에서 생각해 주어야 할 점은 최대공약수를 계산할 때 음수는 양수로 취급한다. 그러나 입력되는 x, y값은 음수도 될 수 있으므로 연산 시에는 절대값을 사용해 주어야 한다.
• 또 x, y에 0이 들어오는 경우도 있기 때문에 0일때의 예외 처리를 따로 해 주어야 한다.

 

 

🔹 타워의 정보를 입력 받는다. 타워의 정보가 입력될 때마다 풍선에 공격을 한다.

• 이 문제가 시간 복잡도가 조금 빠듯하게 설정되어 있는듯 하다. 타워의 정보를 모두 입력 받고 난 다음에 공격을 하면 시간 초과가 발생한다. 입력을 받으면서 공격을 하니까 시간초과가 발생하지 않았다.
• 풍선에 공격할 때에는 풍선들의 체력을 깎아주는 로직이 필요하다. 이를 직접 반복문을 돌면서 체력을 깎아준다면 마찬가지로 시간초과가 발생한다. 
• 정렬과 이분탐색을 사용한다. 정렬로 풍선들의 체력 순으로 오름차순 정렬 한 다음 이분탐색을 통해 현재 누적된 데미지와 mid 인덱스의 값과 비교하여 체력이 남아있을 수 있는 인덱스를 찾아준다.
• mid값이 누적 데미지보다 작거나 같다면 더 큰 부분을 탐색하고 크다면 더 작은 부분을 탐색하도록 하였다.
• 예외 처리 부분은 이미 모든 풍선의 체력이 다 떨어진 상태인지 확인하는 경우와 현재 tower의 방향과 풍선의 방향이 같지 않을때 부분만 처리해 주었다.
• 남아있는 풍선의 개수 정보는 전체 풍선의 개수에서 체력이 남는 최소 인덱스를 빼 준 값이 된다.

 

코드

//22238: 가희와 btd5
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
       
        ArrayList<Integer> bollons_hp = new ArrayList<>();
        int bollon_x = 0;
        int bollon_y = 0;
        for(int i = 0; i < n; i++) {
            str = bf.readLine();
            st = new StringTokenizer(str);
            bollon_x = Integer.parseInt(st.nextToken());
            bollon_y = Integer.parseInt(st.nextToken());
            int hp = Integer.parseInt(st.nextToken());
            bollons_hp.add(hp);
        }
        Collections.sort(bollons_hp);
        int[] bollon_dir = cal_dir(bollon_x, bollon_y);
 
        StringBuilder sb = new StringBuilder();
        int left = 0;
        long total_damage = 0;
        for(int i = 0; i < m; i++) {
            str = bf.readLine();
            st = new StringTokenizer(str);
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int damage = Integer.parseInt(st.nextToken());
            //입력 끝
 
            int[] tower_dir = cal_dir(x, y);
            if (n == left || (tower_dir[0] != bollon_dir[0] || tower_dir[1] != bollon_dir[1])) {
                sb.append(n - left + "\n");
                continue;
            }
 
            int right = n - 1;
            total_damage += damage;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (bollons_hp.get(mid) <= total_damage) left = mid + 1;
                else right = mid - 1;
            }
            sb.append(n - left + "\n");
        }
        System.out.print(sb.toString());
    }
 
    public static int[] cal_dir(int x, int y) {
        if(x == 0 && y == 0) {
            x = 0;
            y = 0;
        }
        else if(x == 0 && y < 0) {
            x = 0;
            y = -1;
        } else if(x == 0 && y > 0) {
            x = 0;
            y = 1;
        } else if(y == 0 && x < 0) {
            x = -1;
            y = 0;
        } else if(y == 0 && x > 0) {
            x = 1;
            y = 0;
        } else {
            int g = gcd(Math.abs(x), Math.abs(y));
            x = x / g;
            y = y / g;
        }
        return new int[] {x, y};
    }
 
    public static int gcd(int x, int y) {
        if(x % y == 0) return y;
        return gcd(y, x % y);
    }
}