[프로그래머스][C++] 카펫

카펫

문제 링크

카펫

분석

brown은 테두리, yellow는 내부이기 때문에 최소 크기는 [3, 3]입니다.
가로 길이는 세로 길이보다 길거나 같아야합니다.

총 격자의 크기는 $brown + yellow$입니다.

갈색 격자가 채워지는 방법은 다음과 같습니다.
모서리를 제외한 가로 면을 채우기 위해선 $노란색 \ 격자 \ 가로 \ 길이 \times 2$개의 갈색 격자가 필요합니다.
모서리를 제외한 세로 면을 채우기 위해선 $노란색 \ 격자 \ 세로 \ 길이 \times 2$개의 갈색 격자가 필요합니다.
모서리는 고정적으로 4칸이므로 4를 더하면 됩니다.

노란색 격자가 채워지는 방법은 다음과 같습니다.
갈색 격자가 채워지는 테두리를 제외한 나머지 모든 칸은 노란색 격자입니다.
즉, 가로 2칸, 세로 2칸을 제외한 $(가로 - 2) \times (세로 - 2)$가 노란색 격자가 됩니다.

풀이

#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    // 격자의 총 개수
    int total = brown + yellow;
    
    // 세로를 기준으로 격자의 총 개수의 약수를 구하는 반복문
    for (int height = 3; height * height <= total; ++height)
    {
        // 약수인지 확인
        if (total % height == 0)
        {
            // 가로 길이를 구합니다.
            int width = total / height;
            
            // 현재 약수에서 세로 길이와 가로 길이로 카펫이 만들어지는지 확인
            if ((2 * width) + (2 * height) - 4 == brown)
            {
                answer.push_back(width);
                answer.push_back(height);
                break;
            }
        }
    }
    
    return answer;
}

격자의 총 개수를 기준으로 세로와 가로의 약수를 구합니다.
약수에서 카펫을 그릴 수 있는 가로와 세로를 구할 수 있습니다.

성능 요약

시간 복잡도는 $O(\sqrt{n})$입니다.

• total에 대한 반복문 $O(\sqrt{n})$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.02ms, 4.54MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.15MB)
테스트 6 〉 통과 (0.01ms, 4.16MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.02ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.13MB)
테스트 10 〉 통과 (0.01ms, 3.68MB)
테스트 11 〉 통과 (0.01ms, 3.59MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 4.05MB)