99클럽 코테 스터디 21일차 TLI-(완전탐색)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42842

제한조건

• 가로>=세로
• 노란색 카펫조각은 갈색 카펫조각으로 둘러 싸여 있다.

🚨오늘의 학습

⭐️완전탐색⭐️

카펫의 가로와 세로가 될 수 있는 모든 경우를 탐색한다

🗝️ 전체 카펫의 조각(brown,yellow)에서 카펫의 가로,세로 길이 찾기

🗝️ 노란색 조각은 갈색에 싸여 있는 형태로 노란색은 항상 전체 -2의 가로,세로 길이를 갖는다

🗝️ 🔅전체 카펫의 조각에서 약수 찾기

// 약수 탐색을 제곱근까지만 수행
        for (long i = 1; i * i <= cnt; i++) {
            if (cnt % i == 0) {
                yagSu.add(i); // 약수 추가
                if (i != cnt / i) {
                    yagSu.add(cnt / i); // 짝이 되는 약수 추가
                }
            }
        }

---

import java.util.*;

public class Carpet {

    /**
     * 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
     * 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
     * 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
     */
    public static void main(String[] args) {
        solution(24,24);
    }

    public static int[] solution(int brown, int yellow) {

        int total = brown+yellow;

        List<Integer> totalYagsu = new ArrayList<>();
        List<Integer> yellowYagsu = new ArrayList<>();

        // 약수 탐색을 제곱근까지만 수행
        for (int i = 1; i * i <= total; i++) {
            if (total % i == 0) {
                totalYagsu.add(i); // 작은 약수 추가
            }
        }

        // 약수 탐색을 제곱근까지만 수행
        for (int i = 1; i * i <= yellow; i++) {
            if (yellow % i == 0) {
                yellowYagsu.add(i); // 작은 약수 추가
            }
        }


        //카펫의 가로, 세로 크기
        int[] answer = new int[2];

        for(int i=0; i<totalYagsu.size();i++){
            if(totalYagsu.get(i)<3){
                continue;
            }
            int width = Math.max(totalYagsu.get(i),(total/totalYagsu.get(i)));
            int height = Math.min(totalYagsu.get(i),(total/totalYagsu.get(i)));

            for(int j=0; j<yellowYagsu.size();j++){
                int yellowHeight = Math.min(yellowYagsu.get(j),(yellow/yellowYagsu.get(j)));
                int yellowWidth = Math.max(yellowYagsu.get(j),(yellow/yellowYagsu.get(j)));

                if(((height-2) == yellowHeight) && ((width-2) ==yellowWidth)){
                    answer[0] = width;
                    answer[1] = height;
                    return answer;
                }

            }

        }
        return answer;
    }

}