[프로그래머스/알고리즘] 카펫

문제 설명

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

해결 방법

저는 값들의 규칙을 찾아서 값을 구했습니다.

카펫에서 가장 최소 brown와 red는 8, 1입니다.

여기서 red를 늘렸을 때를 아래 표처럼 됩니다. *brown, red(가로,세로) 가로, 세로는 리턴값입니다.

8,1(3,3)	10,2(4,3)	12,3(5,3)	14,4(6,3)	16,5(7,3)	18,6(8,3)	20,7(9,3)
X	12,4(4,4)	14,6(5,4)	16,8(6,4)	18,10(7,4)	20,12(8,4)	22,14(9,4)
X	X	16,9(5,5)	18,12(6,5)	20,15(7,5)	22,18(8,5)	24,21(9,5)
X	X	X	20,16(6,6)	22,20(7,6)	24,24(8,6)	26,28(9,6)

여기서 규칙은 내려갈수록 brown는 2씩 증가하고 red는 첫번 째행의 값의 배수가 됩니다.

예로 brown : 18, red : 12를 구하고 싶으면

brown이 18일 때 red가 가장 작은 수를 구합니다.

8,1(3,3)	10,2(4,3)	12,3(5,3)	14,4(6,3)	16,5(7,3)	18,6(8,3)	20,7(9,3)
X	12,4(4,4)	14,6(5,4)	16,8(6,4)	18,10(7,4)	20,12(8,4)	22,14(9,4)
X	X	16,9(5,5)	18,12(6,5)	20,15(7,5)	22,18(8,5)	24,21(9,5)
X	X	X	20,16(6,6)	22,20(7,6)	24,24(8,6)	26,28(9,6)

가로 길이는 는 brown-2/2를 하면 구할 수 있고 세로길이는 3부터 시작합니다.

그 후에 brown과 같은 경우는 18, 10입니다. (왼쪽 아래로 대각선은 항상 brown이 같습니다.)

가로는 1칸이 줄고 세로는 1칸이 늘렸을 경우 brown은 항상 동일해집니다.

red값은 첫번 째 값인 6에서 1을 빼고 배수를 이용해서 구할 수 있습니다.

이 값들이 요구사항인 18, 12가 될 때 까지 반복하면 됩니다. 

소스 코드

#include <string>
#include <vector>
using namespace std;

vector<int> solution(int brown, int red) {
	vector<int> answer;
	int firstx = (brown - 2) / 2;
	int firsty = 3;
	int firstbrown = brown;
	int firstred = firstx-2;
	int lastred= firstx - 2;
	int i = 0;
	while (1) {
		if (lastred == red)
			break;
		i++;
		firstx -= 1;
		firsty += 1;
		lastred = (firstred-i)*(i+1);
	}

	answer.push_back(firstx);
	answer.push_back(firsty);

	return answer;
	
}