[알고리즘] 프로그래머스 카펫 -완전탐색-

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

프로그래머스

 

 

 

 

지인의 추천으로 풀어봤습니다. 완전탐색 옛날 알고리즘 시간에 배운거 같긴한데 따로 푸는건 처음이네요. 근데 완전탐색으로 푼건지는 잘 모르겠네요 ..ㅠ

 

처음에 레드카펫이 직사각형이나 정사각형 모양뿐만 아니라 기역자모양이라든가 니은자 모양 등도 되는줄 알고 그렇게 풀었다가 다시 문제보고 잘못푼걸 알았네요 ㅎㅎ

문제에 다써있는데 실수하는 습관을 줄여야할 것 같습니다. ㅠ

 

처음 메모장으로 다음과 같이 작성했더니 규칙이 보여서 그대로 풀었습니다.

i로 for문을 돌려줍니다. 이 때 i는 레드카펫 세로길이이며 세로길이는 항상 가로길이보다 같거나 짧아야하므로 red/2 만큼만 반복해줍니다.

그리고 정사각형인 경우를 판별하기 위해 i 가 red(레드카펫개수)의 제곱근인지 판별하는 분기처리

그 이후에는 직사각형인지 판별하기 위한 분기처리를 위해 red % i == 0 로 확인해줍니다.

이렇게 분기처리한 후 [전체넓이 - 레드카펫전체개수 = 브라운카펫전체개수] 인지 체크해서 맞다면 그게 답이 됩니다.

 

코드는 다음과 같습니다.

class Solution {

    public static int[] answer = {};

    public int[] solution(int brown, int red) {
        if (red == 1) { //red 1은 for 문 못타므로 따로 처리
            answer = new int[]{3, 3};
            return answer;
        }
        for (int i = 1; i <= red / 2; i++) {
            int redSero = 0;
            int redGaro = 0;
            if (i * i == red) { //제곱 (정사각형)
                redSero = i;
                redGaro = i;
                if ((redSero + 2) * (redGaro + 2) - red == brown) {
                    answer = new int[]{redGaro + 2, redSero + 2};
                    break;
                }
            }
            if (red % i == 0) { //직사각형 처리
                redSero = i;
                redGaro = red / i;
                if ((redSero + 2) * (redGaro + 2) - red == brown) {
                    answer = new int[]{redGaro + 2, redSero + 2};
                    break;
                }
            }
        }
        //전체 가로 세로 크기
        return answer;
    }
}

 

다시보니까 제곱 분기처리 필요 없는 거 같은데... 어,,,

 

 

지인은 다음과 같이 풀었네요. 아직 코드는 안봤는데 길이나 깔끔함을 보니 더 잘 푼 것 같습니다.

https://lifelife7777.tistory.com/49

프로그래머스 - 카펫

 

댓글과 공감은 큰 힘이됩니다 !!!!