[프로그래머스] 카펫 (Lv2)

문제

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

---

고민1. 규칙

약간의 수학적 사고가 필요해보인다.
먼저 찾을 수 있는 규칙은

• 갈색 격자의 수 brown, 노란색 격자의 수 yellow 의 합은 카펫의 가로*세로이다.
  -> brown + yellow = row * column
• 갈색은 테두리에 한 줄로 둘러있으므로 brown은 row과 column로 나타낼 수 있다.
  -> brown = (row-1)+(column-1)+(row-1)+(column-1) = 2*(row+column-2)
• 노란색은 테두리 한 칸씩을 제외한 격자의 수로 (row-2)*(column-2)와 같다.
  -> yellow>=1이므로 row>=3 column>=3

따라서

brown + yellow = 2*(row+column-2) + (row-2)*(column-2) = row * column 
(단, brown>=8, yellow>=1, row>=3, column>=3, row>=column)

고민2. 완전탐색

문제의 카테고리는 완전탐색이다.

완전 탐색이란?

가능한 경우의 수를 모두 나열하면서 원하는 답을 찾는 방법이다.

위 식을 만족하는 row, column을 찾을 때 까지 반목문을 통해 구하면 될 것 같다.

로직
1. total을 구한다(brown + yellow)
2. 먼저 3으로 r을 임의 지정하고 total%r=0이면 c=total/r를 구한다(r로 나누어 떨어지는 몫 c를 구한다).
3. column>=3, row>=column 이 성립하는지 검사한다.
4. brown = 2(row+column-2) 이 성립하는지 검사한다
~~5. yellow = (row-2)(column-2) 이 성립하는지 검사한다.~~ 4번만 검사해도 동일함
6. 모두 성립할 때까지 2~5 과정을 반복한다(2에서 r의 크기를 1씩 증가하며 반복).

코드로 작성하면...

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int total,r,c;
        
        total=brown+yellow;
        
        for(r=3;;r++){
            if(total%r==0){
                c=total/r;
                if(c>=3 && r>=c){
                    if(brown==2*(r+c-2)) break;
                    else continue;
                }
                else continue;
            }
            else continue;      
        }
        
        answer[0]=r;
        answer[1]=c;
        return answer;
    }
}

---

GitHub Java-algorithm-practice/프로그래머스/lv2/42842. 카펫/