λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

[λ°±μ€€/1002/싀버3] ν„°λ ›

μ‹œνλ¦¬ν‹°μ§€ν˜Έ 2024. 2. 25.

https://www.acmicpc.net/problem/1002

1002번: ν„°λ ›

각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€λ§ˆλ‹€ λ₯˜μž¬λͺ…이 μžˆμ„ 수 μžˆλŠ” μœ„μΉ˜μ˜ 수λ₯Ό 좜λ ₯ν•œλ‹€. λ§Œμ•½ λ₯˜μž¬λͺ…이 μžˆμ„ 수 μžˆλŠ” μœ„μΉ˜μ˜ κ°œμˆ˜κ°€ λ¬΄ν•œλŒ€μΌ κ²½μš°μ—λŠ” $-1$ 좜λ ₯ν•œλ‹€.

www.acmicpc.net

 
<<풀이>>
레벨: 싀버 3
 
μ‹œκ°„ λ³΅μž‘λ„ : O(N)
 
μ‹œκ°„: 284ms
 
μ£Όμš” κ°œλ… : Math.sqrt, continue, ArrayList, 두 개의 원이 ν•œ μ›μ˜ 내뢀에 μžˆμ„ λ•Œ λ°”κΉ₯에 μžˆμ„ λ•Œ ꡬ뢄
 
이 λ¬Έμ œλŠ” λ‹¨μˆœ κ΅¬ν˜„ λ¬Έμ œμ΄λ©΄μ„œ μ˜›λ‚ μ— 배운 μˆ˜ν•™μ μΈ 지식이 ν•„μš”ν•œ λ¬Έμ œμ΄λ‹€. λ„ˆλ¬΄ μ˜€λžœλ§Œμ— μ ‘ν•˜λ‹ˆ 경우의 수λ₯Ό 두 원이 λ°–μ—μ„œ 겹치고 μ ‘ν•˜κ³  등을 κ³„μ‚°ν•΄μ„œ μ²˜μŒμ— κ΅¬ν–ˆλ‹€κ°€ ν‹€λ Έλ‹€κ°€ λ‚˜μ™”λ‹€. μ•Œκ³  λ³΄λ‹ˆ, 두 개의 원 쀑 ν•œ 원이 λ‚΄λΆ€μ—μ„œ κ²ΉμΉ˜λŠ” 쑰건도 포함을 μ‹œμΌ°μ–΄μ•Ό ν–ˆλ‹€. 
κ·Έλž˜μ„œ 이λ₯Ό μΆ”κ°€ν•˜κ³  문제λ₯Ό 접근을 ν•΄μ„œ 결과적으둜 풀은 쀄 μ•Œμ•˜λŠ”λ°, 또 ν‹€λ Έλ‹€κ°€ λ‚˜μ™”λ‹€... γ…‹ γ… 
 
λ°”λ‘œ λ¬΄ν•œνžˆ κ²ΉμΉ  λ•Œ -1둜 좜λ ₯ν•˜λΌλŠ” λΆ€λΆ„ λ•Œλ¬Έμ΄μ—ˆλ‹€. λ‚˜λŠ” ν•˜λ‚˜ κ²ΉμΉ λ•Œ, 두 개 κ²ΉμΉ λ•Œ, ν•˜λ‚˜λ„ μ•ˆ κ²ΉμΉ  λ•Œλ₯Ό μ œμ™Έν•˜λ©΄ 무쑰건 -1이 좜λ ₯이 λœλ‹€κ³  μƒκ°ν–ˆλ‹€. ν•˜μ§€λ§Œ μ΄λŠ” 잘λͺ»λœ μƒκ°μ΄μ—ˆκ³  μ™„μ „νžˆ κ²ΉμΉ˜λŠ” κ²½μš°λŠ” 쀑심 점과 λ°˜μ§€λ¦„ 길이 μ „λΆ€κ°€ 같은데 μ΄λŠ” λ‚΄κ°€ κ΅¬ν˜„ν•œ μ½”λ“œμ—μ„œλŠ” 1λ₯Ό λ„μΆœν•΄μ„œ list에 λ„£μ–΄μ€˜λ²„λ¦¬λŠ” λ¬Έμ œκ°€ λ°œμƒν–ˆλ‹€.
 
κ·Έλž˜μ„œ 사전에 μ™„μ „νžˆ κ²ΉμΉ˜λŠ” 경우λ₯Ό μ œμ™Έμ‹œν‚€κ³  μ‹œμž‘ν–ˆλ‹€.
 

if(x[0]==x[3] && x[1]==x[4] && x[2]==x[5]) {
    answer.add(-1);
    continue;
}

 
λ°”λ‘œ 이 뢀뢄이닀. μ΄λ ‡κ²Œ ν’€μ—ˆλ”λ‹ˆ λ¬΄μ‚¬νžˆ 맞좜 μˆ˜κ°€ μžˆμ—ˆλ‹€.
 
 

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    private ArrayList<Integer> solution(ArrayList<int[]> list2) {
        ArrayList<Integer> answer = new ArrayList<>();
        for (int[] x : list2) {
            if(x[0]==x[3] && x[1]==x[4] && x[2]==x[5]) {
                answer.add(-1);
                continue;
            }
            if(Math.sqrt((x[0]-x[3])*(x[0]-x[3]) + (x[1]-x[4])*(x[1]-x[4])) > Math.max(x[2], x[5])) {
                if (Math.sqrt((x[0] - x[3]) * (x[0] - x[3]) + (x[1] - x[4]) * (x[1] - x[4])) == (x[2] + x[5])) {
                    answer.add(1);
                } else if (Math.sqrt((x[0] - x[3]) * (x[0] - x[3]) + (x[1] - x[4]) * (x[1] - x[4])) < (x[2] + x[5])) {
                    answer.add(2);
                } else if (Math.sqrt((x[0] - x[3]) * (x[0] - x[3]) + (x[1] - x[4]) * (x[1] - x[4])) > (x[2] + x[5])) {
                    answer.add(0);
                }
            } else {
                if (Math.sqrt((x[0] - x[3]) * (x[0] - x[3]) + (x[1] - x[4]) * (x[1] - x[4])) + Math.min(x[2], x[5]) == Math.max(x[2], x[5])) {
                    answer.add(1);
                } else if (Math.sqrt((x[0] - x[3]) * (x[0] - x[3]) + (x[1] - x[4]) * (x[1] - x[4])) + Math.min(x[2], x[5]) > Math.max(x[2], x[5])) {
                    answer.add(2);
                } else if (Math.sqrt((x[0] - x[3]) * (x[0] - x[3]) + (x[1] - x[4]) * (x[1] - x[4])) + Math.min(x[2], x[5]) < Math.max(x[2], x[5])) {
                    answer.add(0);
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int test = in.nextInt();
        ArrayList<int[]> list1 = new ArrayList<>();
        ArrayList<int[]> list2 = new ArrayList<>();
        for (int i = 0; i < test; i++) {
            list1.add(new int[6]);
        }
        for(int[] a : list1) {
            for (int i = 0; i < 6; i++) {
                a[i] = in.nextInt();
            }
            list2.add(a);
        }

        for (int answer : T.solution(list2) ) {
            System.out.println(answer);
        }
    }
}

 
λ‹€λ₯Έ μ‚¬λžŒλ“€μ€ λ‚˜ 284ms보닀 λΉ λ₯΄κ²Œ κ΅¬ν˜„μ„ ν•œ κ±° 같은데 ν•œ 번 찾아봐야겠닀 !
 
<<μΆ”κ°€ 곡뢀>>
κΉŒλ¨Ήμ–΄μ„œ λ‹€μ‹œ ν•œ 번 μ •λ¦¬ν•˜κ³  κ°„λ‹€!!
 
break : 돌고 있던 λ°˜λ³΅λ¬Έμ„ μ™„μ „νžˆ μ’…λ£Œ μ‹œν‚€κ³  λ‹€μŒ 단계λ₯Ό μ§„ν–‰ν•œλ‹€.
 
continue : λ”이상 λ°‘μœΌλ‘œ μ§„ν–‰ν•˜μ§€ μ•Šκ³  for문의 λ‹€μŒ 단계λ₯Ό μ§„ν–‰ν•œλ‹€.
 
return: λ©”μ„œλ“œ 전체λ₯Ό μ’…λ£Œμ‹œν‚¨λ‹€.
 
μ’€ 더 λ””ν…ŒμΌν•œ 정리

  • break: ν˜„μž¬ μ‹€ν–‰ 쀑인 반볡문 (예: for, while, do-while 루프)을 μ™„μ „νžˆ μ’…λ£Œμ‹œν‚€κ³ , 반볡문 λ°”λ‘œ λ‹€μŒμ— μœ„μΉ˜ν•œ μ½”λ“œμ˜ 싀행을 κ³„μ†ν•©λ‹ˆλ‹€. switch λ¬Έ λ‚΄μ—μ„œλ„ μ‚¬μš©λ˜μ–΄, case λΈ”λ‘μ˜ 싀행을 μ’…λ£Œν•˜κ³  switch 문을 λΉ μ Έλ‚˜μ˜΅λ‹ˆλ‹€.
  • continue: continueκ°€ ν¬ν•¨λœ 반볡문의 ν˜„μž¬ μ‹€ν–‰ 쀑인 λ°˜λ³΅μ„ μ¦‰μ‹œ μ’…λ£Œν•˜κ³ , 반볡문의 λ‹€μŒ 반볡으둜 κ±΄λ„ˆλ›°μ–΄ 계속 μ‹€ν–‰ν•©λ‹ˆλ‹€. for λ£¨ν”„μ˜ 경우, μ¦κ°μ‹μœΌλ‘œ μ΄λ™ν•˜κ³ , while λ˜λŠ” do-while λ£¨ν”„μ˜ 경우, μ‘°κ±΄μ‹μœΌλ‘œ λŒμ•„κ°‘λ‹ˆλ‹€.
  • return: ν˜„μž¬ μ‹€ν–‰ 쀑인 λ©”μ„œλ“œλ₯Ό μ’…λ£Œν•˜κ³ , λ©”μ„œλ“œλ₯Ό ν˜ΈμΆœν•œ 곳으둜 μ œμ–΄λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€. void λ©”μ„œλ“œμ—μ„œλŠ” λ‹¨μˆœνžˆ λ©”μ„œλ“œ 싀행을 μ’…λ£Œν•˜λ©°, λ°˜ν™˜ νƒ€μž…μ΄ μžˆλŠ” λ©”μ„œλ“œμ—μ„œλŠ” 값을 λ°˜ν™˜ν•©λ‹ˆλ‹€. return 문을 λ§Œλ‚˜λ©΄, κ·Έ λ¬Έμž₯ μ΄ν›„μ˜ λ©”μ„œλ“œ λ‚΄ μ½”λ“œλŠ” μ‹€ν–‰λ˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

λŒ“κΈ€