https://programmers.co.kr/learn/courses/30/lessons/42842
접근
카테고리를 소인수 분해라고 달았지만 풀이에는 쓰지 않았습니다.
규칙을 살펴보면 다음과 같은 규칙이 있습니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
만약 저 조건이 없다면 가능한 답이 1개 이상 나올 수 있습니다.
예를 들어 brown = 10 , red = 2 라는 예제에서 위 조건이 없다면
red가 중간에서 가로로 뻗어있는 모양일 때 [4,3]이 답이며
red가 중간에서 세로로 뻗어있는 모양일 때 [3,4]도 답이 됩니다.
따라서 위 조건은 빨간 블록은 정사각형 혹은 가로 모양의 직사각형 이다. 라는 조건으로 해석이 가능합니다.
그럼 다시 빨간 블록으로 돌아와서, 가능한 빨간블록의 경우는 여러가지가 나올 수 있습니다.
예를들어 red = 24 라면
24 x 1
12 x 2
8 x 3
6 x 4
로 표현이 가능하며
이때 필요한 갈색블록의 개수는 빨간 블록의 총 가로길이를 a, 세로길이를 b 라 하였을때
(2a) + (2b) +4 가 됩니다.
(빨간색 가로길이 만큼 위,아래 , 세로길이만큼 왼쪽,오른쪽, 비어있는 귀퉁이 4블록)
따라서 red를 가능한 2개의 자연수 곱셈으로 나타낼수 있는 모든 경우 중에서
좌측이 우측보다 큰 경우만 고려하면 됩니다.
이때 (2a) + (2b) +4 == brown을 만족하면 정답이며 정답은
[(a+2) , (b+2)]가 됩니다.
소인수 분해를 사용해야 되나 했지만 red의 최대값이 200만 이므로 만약 200만부터 1씩 감소하면서(혹은 1부터 1씩 증가하면서) 검사한다 해도 1초안에 처리가능한 연산이라고 생각되어 그냥 진행했습니다.
다음은 코드 전문입니다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int red) {
vector<int> answer;
for(int i = red ; i >= (red/i) ; i--){
if (red%i != 0) {
continue;
}
if (((2*i)+(2*(red/i))+4) == brown) {
answer.push_back(i+2);
answer.push_back((red/i)+2);
break;
}
}
return answer;
}