[고득점Kit][완전 탐색] 카펫 ⭐⭐

[완전 탐색] 카펫

난이도 ⭐⭐

문제

내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int width, height;
    
    for(int i = 1; ; i++)
    {
        if (yellow  % i != 0)
            continue;
        
        width = yellow / i;
        height = i;
        
        if(width < height)
            break;
        else
        {
            for(int j = 1; ; j++)
            {
                if((width + 2 * j) * (height + 2 * j) - yellow == brown)
                {
                    answer.push_back(width + 2 * j);
                    answer.push_back(height + 2 * j);
                    
                    return answer;
                }
                else if ((width + 2 * j) * (height + 2 * j) - yellow > brown)
                {
                    break;
                }
            }
        }
    }
}

• 카펫은 가로 길이 >= 세로 길이이어야 한다.
• width와 height은 yellow 의 가로 세로 길이의 후보.
  • yellow 행열 후보는 width >= height을 만족함과 동시에 width * height == yellow가 되야 한다. 즉, width, height은 yellow의 약수가 된다.
    • width보다 짧아도 되는 height을 1 부터 시작하여 차례 차례 yellow의 약수들로 업뎃하여 여러 후보들 중 적합한 width와 height을 가지는 yellow를 찾아야 한다.
  • yellow 의 적합한 width와 height 찾는 기준
    • brown을 yellow의 겉 테두리에 한 줄씩 추가해본다.
      • 양 옆에 추가 되니까 + 2
    • 그러면 전체 카펫의 격자 개수는 총 (width + 2*1) X (height + 2*1) 가 된다.
      • 이 전체 카펫의 격자 개수 - yellow == brown
        • 일치하다면 적합한 width와 height을 찾은 것!
        • 이때 전체 카페의 가로 세로를 각각 answer에 추가한 뒤 리턴하고 끝내면 됨.
      • 이 전체 카펫의 격자 개수 - yellow > brown
        • yellow의 width와 height을 좀 더 크게 잡아야 하므로 break 하고 다음 width height 후보로
          • 첫번재 for문의 다음 i로
      • 이 전체 카펫의 격자 개수 - yellow < brown
        • brown 이 되려면 아직 부족하므로 갈색 격자를 한 줄 더 추가로 두른다.
          • 두번째 for문의 다음 j로
• brown = 48, yellow = 16 를 예로 들어보자면
  • i = 1
    • i = height = 1 👉 width = 16
      • width >= height 이므로 계속 진행한다.
      • j = 1 👉 yellow 주변에 갈색 격자들 한 줄 두른다.
        • (16 + 2) X (1 + 2) = 54 - 16 = 38 < 48 이므로 적합하지 않다. 갈색 한 줄 더 둘러야 한다.
      • j = 2 👉 yellow 주변에 갈색 격자들 한 줄 추가로 두른다.
        • (16 + 4) X (1 + 4) = 100 - 16 = 84 > 48 이므로 적합하지 않다.
    • i = height = 2 👉 width = 8
      • width >= height 이므로 계속 진행한다.
      • j = 1 👉 yellow 주변에 갈색 격자들 한 줄 추가로 두른다.
        • (8 + 2) X (2 + 2) = 40 - 16 = 24 < 48 이므로 적합하지 않다. 갈색 한 줄 더 둘러야 한다.
      • j = 2 👉 yellow 주변에 갈색 격자들 한 줄 추가로 두른다.
        • (8 + 4) X (2 + 4) = 72 - 16 = 56 > 48 이므로 적합하지 않다.
    • i = height = 3 👉 3 은 yellow 의 약수가 아니므로 정수인 width를 구할 수 없다.
    • i = height = 4 👉 width = 4
      • width >= height 이므로 계속 진행한다.
      • j = 1 👉 yellow 주변에 갈색 격자들 한 줄 추가로 두른다.
        • (4 + 2) X (4 + 2) = 36 - 16 = 20 < 48 이므로 적합하지 않다. 갈색 한 줄 더 둘러야 한다.
      • j = 2 👉 yellow 주변에 갈색 격자들 한 줄 추가로 두른다.
        • (4 + 4) X (4 + 4) = 64 - 16 = 48 == 48 이므로 yellow가 width = 4, height = 4 이고 주변에 갈색 테두리를 2 줄씩 둘렀을 때인 이 때의 케이스가 정답이 된다.
          • 정답 [8, 8]

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기