[알고리즘 문제 풀이] 프로그래머스 - 카펫

원문 링크: programmers.co.kr/learn/courses/30/lessons/42842

카테고리: 완전탐색

 

문제 설명

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

레오는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했다. 레오가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성하라. 

 

제한사항

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

입출력 예

int brown = 10; int yellow = 2; // return [4,3];
int brown = 8; int yellow = 1; // return [3,3];
int brown = 24; int yellow = 24; // return [8,6];

 

풀이 과정

생각보다 쉽게 풀었다. 먼저 그림을 그려가며 어떤 로직을 사용할지 고민했다. 노란색의 격자를 1줄로 놓는 케이스부터 시작해서 점점 늘려가며 갈색 격자를 감싸는 모양이 되는지 확인하면 된다. 큰 틀은 for문을 이용해 1부터 늘려가며 검사하는 방식이다. 

일단 brown에서 4를 빼면 네 모서리의 격자를 뺀 나머지 갈색 격자의 숫자 frame를 구할 수 있다. 그러면 frame의 값이 아래의 값과 일치할 때가 바로 우리가 찾는 갈색과 노란색 격자의 조합이 된다. 

 

frame = (세로 격자 높이 x 2) + (가로 격자 길이 x 2)

 

자바 코드

public int[] solution(int brown, int yellow) {
    int[] answer = {0, 0};

    // frame = (2 x horizontal) + (2 x vertical)
    int frame = brown - 4; // 네 모서리의 한 칸씩을 뺀 나머지

    for (int vertical = 1; vertical <= frame / 4; vertical++) {
        if (yellow % vertical == 0) {
            int horizontal = yellow / vertical;

            int check = (2 * horizontal) + (2 * vertical);
            if (frame == check) {
                answer[0] = 2 + horizontal;
                answer[1] = 2 + vertical;
                break;
            }
        }
    }

    return answer;
}

채점 결과

 

참고

- 깃허브 소스 코드: 링크