카펫 - 42842

https://github.com/GyungSikHan/AlgorithmTest/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42842.%E2%80%85%EC%B9%B4%ED%8E%AB

AlgorithmTest/프로그래머스/2/42842. 카펫 at main · GyungSikHan/AlgorithmTest

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    for(int i = 1; i <= yellow; i++)
    {
        int x = yellow / i;
        if(yellow % i == 0)
        {
        	if(brown == 2*x+ 2*i+4)
        	{
            	answer.push_back(x+2);
            	answer.push_back(i+2);
            	break;
        	}
        }
    }
    return answer;
}

• 아이디어가 떠오르지 않아 꽤 애를 먹었다

 

• 일단 yellow의 가로를 x, 세로를 y 라 한다면 yellow의 넓이는 x*y일것이다
• 그렇다면 x = yellow/y가 될것이다
• 이를 활용해 brown의 값을 구할 수 있는데 (x+2)*(y+2)-xy로 그 이유는 카펫의 패턴의 특징에 있다
• x+2, y+2에서 +2를 하는 이유는 가운데 yellow가 들어가는 카펫은 겉에 brown 색이 yellow의 가로,세로보다 무조건 +2가 된 값을 갖게된다
  • 이해가 되지 않는다면 여러개 패턴을 그려보면 쉽게 이해된다
• 이제 전체 넓이인 (x+2)*(y+2)에 yellow인 xy 뺀다 생각하면 brown의 넓이를 구할 수 있는데, 이렇게 나온 점화식이 (x+2)(y+2)-xy 이다
• 이를 활용해 전체 카펫의 가로 세로를 구할 수 있는데, 이때 생각해봐야하는 문제가 yellow/y 가 나머지가 0인 딱 나누어 떨어지는 수여야 한다
• 이를 모두 충족하게 구현한다면 위의 코드가 나온다
• 이때 for문을 돌려 모든 조건을 충족한다면 break로 반복문을 종료하는 이유는 점화식을 풀어보면 기본적으로 x,y값이 2가지가 존재하는데 문제 조건에서 가로가 무조건 세로보다 크다는 조건을 만족하기 위해서 반복문에서 조건을 모두 충족하는 가장 작은 i 값을 구하여 반복문을 종료하는 것이다
• 마찬가지로 answer의 x,y에 +2를 하는 이유는 위의 설명했듯이 패턴때문이다

//코드에서 i 를 사용했지만 y라 생각하면 됨