[프로그래머스] 카펫

1. 문제

---

프로그래머스

2. 풀이 과정

---

카펫의 형태가 위와 같이 중앙에는 노란색, 테두리 1줄은 갈색이 칠해져 있다고 할 때,  갈색과 노란색 타일의 갯수를 통해 카펫의 가로, 세로의 길이를 구하는 문제이다.

 

일단 나는 노란색 타일의 집중을 했다.

왜냐하면 노란색 타일의 모양에 따라 필요한 갈색타일의 갯수가 달라지기 때문이다.

예를 들어, 노란색 타일이 4개 있다고 하면, 노란색 타일의 모양은 1 X 4의 형태도 되고 2 X 2도 가능하다.

 

이때, 카펫을 만들기 위해 필요한 갈색 타일의 갯수는 서로 다르다.

• 1 X 4의 경우 갈색은 14개
• 2 X 2의 경우 갈색은 12개

노란색 타일의 가로, 세로 갯수와 갈색 타일의 갯수와의 일반항을 구하면

노란색 타일의 가로길이가 a, 세로길이가 b라고 할 때,

갈색 타일의 갯수는 2 ( a + b) + 4이다.

 

갈색타일은 일단 노란색 타일의 변 주위에 하나씩 있어야 한다. 따라서 노란색 타일의 둘레의 길이인 2(a + b)

또한 꼭짓점에 하나씩 필요하므로 +4이다.

 

일반항까지 구했다면 이문제는 끝났다.

노란타일의 갯수를 통해 가능한 모든 가로, 세로 길이 조합을 조사하면서 갈색 타일의 갯수가 문제에서 주어진 갈색 타일의 갯수와 일치하는 경우를 찾으면 된다.

 

3. 내 코드

---

class Solution {
    public int[] solution(int brown, int yellow) {
        
        for(int i = 1; i <= yellow; i++) {
            if(yellow % i == 0) {
                int ver = i;
                int hor = yellow / i;
                
                if(2 * ver + 2 * hor + 4 == brown){
                    return new int[]{hor + 2, ver + 2};
                }
            }
        }
        
        return null;
    }
}

시간 복잡도

• O(N)