이 문제는 공식을 생각해내야 된다.
문제에 제시된 그림을 봤을 때, y-가로x2, y-세로x2 + 4(모서리) = brown 임을 알 수 있었다.
yellow 카펫의 가로길이를 x, yellow 카펫의 세로길이를 y라고 했을 때, 2(x+y) + 4 = 전체 브라운 타일의 개수
따라서 tmp 변수에 x+y 의 값을 저장해놨다.
int tmp = (brown-4)/2;문제에서 구해야하는건 전체 카펫의 가로와 세로 길이이다.
전체 카펫의 가로는 yellow 카펫의 가로길이+2,
전체 카펫의 세로는 yellow 카펫의 세로길이+2
임을 금방 알 수 있었다.
따라서 x+y = brown 타일의 개수의 조건을 만족시키는 쌍 중에 답이 있을 것이다.
입출력 예, brown = 24, yellow = 24, return = [8,6]
이때, 문제 조건에서 카펫의 가로 길이 >= 카펫의 세로 길이라는 제한사항이 있으므로 x+y = 10(tmp) 일 경우
조건에 만족하는 쌍은,
- (9,1)
- (8,2)
- (7,3)
- (6,4)
- (5,5)
였다.
이 중 적절한 한 쌍을 골라야한다.
이때, y-가로 x y-세로 = yellow 의 조건을 만족하는 쌍을 찾으면 된다!
따라서 위의 예시 쌍중 xy = 24 인 조건을 만족하는 쌍은 (6,4) 이다.
앞서 언급했다시피,
- 전체 카펫의 가로는 yellow 카펫의 가로길이+2
- 전체 카펫의 세로는 yellow 카펫의 세로길이+2
이므로 전체 타일의 가로, 세로는 [8, 6] 임을 도출해낼 수 있다.
[전체코드]
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
// yellow 2, brown 10
// -> y-가로x2, y-세로x2 + 4(모서리) = brown
// y-가로+2, y-세로+2 => 전체 카펫의 가로, 세로
// y-가로 x y-세로 = y
// 가로 >= 세로
// 2x+2y = 20, x+y=10 // (9,1) (8,2) (7,3) (6,4) (5,5)
int tmp = (brown-4)/2;
vector<pair<int, int>> now;
for(int i=1; i<brown; i++) {
if (i>tmp-i) break;
if ((tmp-i)*i == yellow)
now.push_back({tmp-i, i});
}
answer.push_back(now[0].first+2);
answer.push_back(now[0].second+2);
return answer;
}