[프로그래머스 Level 2] [완전탐색] 카펫 (C++)

안녕하세요! 코딩하는 경제학도 쏘코입니다.

오늘 풀어본 문제는 완전탐색의 마지막 문제인 카펫입니다.

 

출처 : 프로그래머스 코딩테스트 연습 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

목차

• 0. 문제 설명
  • 0.0. 제한사항
  • 0.1. 입출력 예
• 1. 풀이 과정
• 2. 소스 코드
• 3. 후기

---

0. 문제 설명

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

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

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

 

0.0. 제한사항

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

0.1. 입출력 예

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

---

1. 풀이 과정

풀고 나서 왜이렇게 복잡하게 생각했지 하는 생각이 들었습니다...

기본적으로 알아야 할 것은 return값에 들어갈 두 값의 합은 brown과 yellow의 합이라는 것과 yellow타일은 brown타일로 둘러싸였기 때문에 return값에서 각각 -2씩을 해준 값들을 곱하면 yellow만 나와야 한다는 것입니다. 

 

그래서 저는 두 가지의 순서로 진행했는데,

첫 번째는 brown과 yellow를 더한 total의 약수를 담은 vector를 만들고

두 번째는 곱했을 때 total이 되는 약수들에 -2씩 해서 곱한 것이 yellow가 나오는 지 확인했습니다.

 

먼저 약수를 구하기 위해서 total을 나눠줍니다. 이전 문제와 동일하게 total의 제곱근까지만 나눠주면 절반은 해결됩니다.

이제 나머지 절반을 구하기 위해서 total에서 앞에서 구한 약수를 나눠줍니다. 그 값들을 넣어줍니다. 저는 순서를 맞춰주기 위해서 for문을 거꾸로 돌렸는데, 그냥 넣고 sort해도 됩니다.

 

이제 곱했을 때 total이 되는 약수짝들에 -2씩 해서 곱한 것이 yellow가 되는지 확인합니다. 이 조건이 붙는 이유는 처음에 설명했으므로 넘어가도록 하겠습니다.

약수들을 구할 때 total의 제곱근을 2번 넣어준 이유가 여기서 대칭으로 곱했기 때문입니다. total의 제곱근 * total의 제곱근 = total이라는 상황을 만들어주기 위해서이죠.

 

yellow가 나오면, answer에 두 값을 넣어줍니다. 큰 수를 먼저 넣고(가로) 작은 수(세로)를 넣어줍니다. 이건 제한사항에 나와있는 내용이기 때문에 순서를 바꾸면 안됩니다!

---

2. 소스 코드

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

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    vector<int> divisor;
    divisor.push_back(1); // 1은 모든 수의 약수니까
    int total = brown + yellow;
    
    // 1. 약수 구하기 (total의 제곱근은 2번 들어가야함!)
    for(int i = 2; i <= sqrt(total); ++i){
        if(total % i == 0){
            divisor.push_back(i);
        }
    }
    
    for(int i = divisor.size()-1; i >= 0; --i)
        divisor.push_back(total/(divisor[i]));
    
    // 2. 곱했을 때 total이 되는 약수들에 -2씩 해서 곱한 것이 yellow가 나오는지 확인
    for(int i = 1; i < divisor.size()/2; ++i){ // 어짜피 1은 아닐테니 1부터 시작
        if ((divisor[i]-2) * (divisor[divisor.size()-1-i]-2) == yellow){
            answer.push_back(divisor[divisor.size()-i-1]);
            answer.push_back(divisor[i]);
            break;
        }
    }
    return answer;
}

---

3. 후기

재미있는 문제였습니다. 엄청 어려워 보이면서도, 이전 문제를 풀었다면 수월하게 접근할 수 있는 문제이기도 했습니다. 문제를 꼼꼼히 읽고 어째서 이런 return값이 나왔는지만 확인하면 그 다음부터는 쉬운 문제였습니다. 하지만 저처럼 굳이 for문 안에서 복잡하게 하지 마시고 (divisor[divisor.size()-i-1 처럼...) algorithm 헤더의 sort를 이용한다면 보다 보기 좋게 만들 수도 있어 보입니다!