[2025.02.18] 카펫

문제 설명

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

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

 

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

 

 

제한사항

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

 

 

입출력 예

brown			yellow	return
10			2	[4, 3]
8			1	[3, 3]
24			24	[8, 6]

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    // yellow의 약수 찾기
    for(int i=1; i<=sqrt(yellow); i++)
    {
        // i가 yellow의 약수라면
        if(yellow%i==0)
        {
            // 갈색 격자의 수 계산
            int expected_borwn=i*2+yellow/i*2+4;
            
            // 갈색 격자의 수가 맞다면
            if(expected_borwn==brown)
            {
                // 카펫 가로, 세로 길이 정답에 저장
                answer.push_back(yellow/i+2);
                answer.push_back(i+2);
                break;
            }
        }
    }
    
    return answer;
}

yellow가 2이나 1일 때는 노란색의 개수 만으로도 모양이 정확히 파악되지만 그보다 숫자가 커지면 노란색 격자모양이 어떻게 되어 있었는지 정확하게 파악할 수 없다. 입출력 예 3번만 보아도 yellow가 24면 24*1, 12*2, 8*3, 6*4로 여러 개의 모양이 나올 수 있다. 이 모양을 확정할 수 있는것은 brown 격자의 수 이다.

8*3(yellow=24, brown=26)	6*4(yellow=24, brown=24)

위 처럼 yellow의 개수는 같지만 모양이 달라지면 brown의 개수가 달라진다. 즉, 알맞은 yellow 영역의 모양을 찾기 위해서는 brown 격자의 개수가 필요하다는 것이다. 가능한 모든 yellow 영역의 모양을 확인하고 그 때의 brown의 개수를 구하여 비교하면 결론적으로 카펫의 정확한 모양을 구할 수 있다.

 

노란 영역의 가로, 세로 길이는 결국 yellow의 약수일 것이다. 이전에도 약수를 구할 때는 항상 반복문을 사용하였다. 단 이번에 약수를 구할 때는 반복문을 yellow까지 돌지 않을 것이다. 어차피 yellow의 영역은 가로가 더 길거나 가로와 세로 길이가 같기 때문에 전부를 돌 필요 없이 절반만 돌면 된다. 또한 제한 사항을 보면 yellow의 값의 제한이 꽤나 큰 것을 알 수 있다. 그래서 i는 1부터 sqrt(yellow)까지만 돌아가게 한다.

 

이 뒤로는 별로 어렵지 않다. yellow를 i로 나누어 나머지를 확인하고 나머지가 0일 때 즉, 나누어 떨어질 때 i는 yellow의 약수이다. 약수라면 brown의 개수를 계산한다. 갈색 격자의 수는 아래와 같은 식으로 계산할 수 있다.

i * 2 + yellow / i * 2 + 4

이렇게 계산한 brown의 격자 수를 매개변수로 들어온 brown과 비교한다. 둘이 같다면 이 모양이 맞기 때문에 answer에 yellow 격자의 가로와 세로 길이를 저장한다. 물론 반복문도 중간에 나오도록 하다. 이때 i는 1부터 시작하여 약수 중에서도 작은 수가 i일 것이다. 따라서 값을 저장할 때 i+2부터 저장하는 것이 아니라 yellow/i+2를 먼저 저장한다. 이 값이 더 크기 때문이다.

 

참고 사항

저번에 약수를 구하는 반복문에서 반복의 수를 최대한 줄이기 위해 아래와 같은 방법을 사용하였다.

https://iiblueblue.tistory.com/194

[2025.01.30] 기사단원의 무기

number의 약수를 구할 때 1~number까지 반복문에서 모두 도는 것이 아니라 1~number/2까지 반복문을 도는 것이다. 

 

이 방법 말고도 약수를 구할 때 반복의 수를 더 줄일 수 있는 방법은 number의 제곱근까지 반복을 도는 것이다. 단, sqrt(number)의 수도 포함하여 반복한다. 예를 들어 9가 number라고 하면 3까지도 반복문에 돌려야하기 때문이다.

 

즉, 아래의 순서로 더 적게 반복문을 돌 수 있다.

• 1~sqrt(number)
• 1~number/2
• 1~number

 

 

문제 링크

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

프로그래머스