[프로그래머스 | Java Lv.2] 카펫 (완전 탐색)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=java

프로그래머스

 

 

중앙에 노란색 타일이 있고, 갈색 타일이 감싸고 있는 형태.

노란색과 갈색 타일의 개수가 주어지면, 전체 타일의 가로/세로 길이를 반환해야 하는 문제

---

접근

 

 전체 타일의 수를 먼저 구하고, 최소공배수로 나올 수 있는 가로*세로 조합을 모두 찾은 후, 노란색과 갈색 타일의 개수가 일치하는 경우를 찾는 방식으로 하면 되지 않을까?

 

 

최종 코드 

package week4.baek.exhaustivesearch;

import java.util.ArrayList;
import java.util.Collections;

public class Carpet {
    public static int[] solution(int brown, int yellow) {
        int[] answer = new int[2];

        int all = brown + yellow;

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= (int)Math.sqrt(all); i++) {
            if(all % i == 0) {
                list.add(i);
                if(all / i != i)
                    list.add(all/i);
            }
        }

        Collections.sort(list);
        System.out.println(list);

        for (int i = 0; i < list.size(); i++) {
            int x = list.get(i);
            //y가 가로(더 크니까)
            int y = all / x;

            //가로는 무조건 3 이상이어야 함
            if(y < 3) continue;

            // (가로-2)*(세로-2) = 노랑색 개수
            if((y-2) * (x-2) == yellow) {
                answer[0] = y;
                answer[1] = x;
                System.out.print("answer[0] = " + answer[0]);
                System.out.println("answer[1] = " + answer[1]);
                break;
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        System.out.println(solution(10, 2));
    }
}

---

https://woodadada16.tistory.com/24

[Java] 약수 구하기 알고리즘