BOJ 3034 - 앵그리 창영

문제

W x H 크기의 직사각형 상자에 N개의 성냥이 들어갈 수 있는지 각각 판별하라.

입력

첫째 줄에 N, W, H, 이후 N줄에 각 성냥의 길이가 주어진다.

출력

각 성냥에 대해 들어가면 "DA", 아니면 "NE"를 출력한다.

예제

입력	출력
`5 3 4` `3` `4` `5` `6` `2`	`DA` `DA` `DA` `NE` `DA`

풀이

상자의 대각선 길이와 성냥 길이를 비교하여 판별한다.

상자의 대각선 길이의 제곱 W² + H²를 구한다
각 성냥 길이의 제곱이 대각선 제곱 이하이면 "DA", 초과이면 "NE"를 출력한다

핵심 아이디어: 직사각형 상자에 넣을 수 있는 최대 길이는 대각선이므로, L² <= W² + H²이면 수납 가능하다.

코드

package day749;
 
import java.io.*;
import java.util.*;
 
public class Day740BOJ3034앵그리창영 {
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    StringBuilder sb = new StringBuilder();
 
    int[] n = new int[3];
    for (int i = 0; i < 3; i++) {
      n[i] = Integer.parseInt(st.nextToken());
    }
    int std = n[1] * n[1] + n[2] * n[2];
    for (int i = 0; i < n[0]; i++) {
      int num = Integer.parseInt(br.readLine());
      sb.append((num * num <= std) ? ("DA\n") : ("NE\n"));
    }
    System.out.println(sb);
  }
}

복잡도

시간: O(N)
공간: O(1)

문제