AlgorithmProgrammers

프로그래머스 카펫

, ,

1. 문제 링크

1.1. 프로그래머스 카펫 문제

2. 문제 조건

문제 설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

2.1. 제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

2.1. 컴퓨팅적 사고

  • 이문제의 핵심은 카펫간의 규칙을 찾아내는것이 급선무입니다.
  • 첫번째 테스트케이스 brown 10, yellow 2 일 경우 가로 일경우 [4,3] 세로일 경우 [3,4]의 값이 반환됩니다. 이것이 뜻하는 바는 yellow가 직사각형이거나 정사각형일 수 있다는것을 뜻하게 됩니다. 즉, 노란블록은 정사각형또는 직사각형으로 가능합니다. 그이유는 n > m 카펫의 가로길이는 세로 길이와 같거나 길기때문입니다.

이것을 어떻게 표현할 수 있을까요?
yellow = 24 테스트케이스를 살펴봅시다.
yellow가 24일 경우 나타낼 수 있는 케이스는(24 * 1, 12 * 2, 8 * 3, 6 * 4)로 표현할 수 있습니다.
즉, 노란블록의 총 가로 길이를 a, 세로길이를 b 라고 봤을때 (2a) + (2b) + 4 로 표현할 수 있습니다. 잘 생각해보시면 노란색 위아래로 갈색블록과 노란색 좌우로 갈색블록이기때문에 총 가로길이 2a, 총 세로길이 2b, 전체 카펫의 좌측 상단, 우측상단, 좌측하단, 우측하단 의 개수 총 4개로 표현 할 수 있습니다.

결과적으로, (2a) + (2b) + 4 의 조건이 성립됩니다.

이에 따라 (2a) + (2b) + 4 의 값이 brown의 개수와 같다는 조건이 성립하면 되겠죠?
즉, 현재 a + 2(끝에 두점) , b + 2(끝에 두점)의 값으로 가로,세로의 최종길이를 구할 수 있게됩니다.

요약

  • 카펫의 길이는 n>m의 크기를 만족합니다.
  • 노란카펫은 직사각형 또는 정사각형을 만족합니다.
  • (2a) + (2b) + 4 의 조건이 brown과 같을때 해당 가로,세로의 최종길이입니다.

2.2. 풀이

2.2.1. 완전탐색 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class 카펫 {
    public static void main(String[] args) {
        int[] answer = new int[2];

        int brown = 10;
        int yellow = 2;

        for(int i=yellow; i >= (yellow/i); i--){
            // 나눠지는값이 아니면분리 못
            if(yellow % i != 0){
                continue;
            }
            // 가로 2배, 세로2배 모서리 4개 추가
            if(((2*i)+(2*(yellow/i)) + 4) == brown){
                answer[0] = 2+i;        // 가로 + 2 끝점
                answer[1] = (2+(yellow/i)); // 세로 +2 끝점
                break;
            }
        }
        System.out.println(answer[0] + ""+ answer[1]);

    }
}
Share