[Programmers/프로그래머스 lv2][C++] 카펫

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스 카펫

프로그래머스 카펫

 

문제 내용

위의 사진과 같이 안쪽에 노란색 칸들이 있고, 이를 1줄로 감싼 갈색 칸들이 있다.

갈색 칸의 개수와 노란색 칸의 개수가 주어질 때, 전체 카펫의 가로, 세로 길이를 구하면 된다.

 

문제 풀이

프로그래머스 카펫 풀이

문제의 상황을 그림 그려보면 위와 같다.

우리는 a와 b에 어떤 값이 들어가면 되는지를 찾으면 쉽게 문제를 해결할 수 있다.

이때 갈색 격자의 수는 8~5,000, 노란 격자의 수는 1~2,000,000라고 한다.

즉 2a*2b+4 <= 5000, a*b <= 2000000이다.

정리하자면 아래와 같다.

a+b <= 2498
a*b <=2000000

브루트포스로 a,b를 구할 것이기 때문에, 그냥 for문 범위를 1~2498로 했다. 2498*2498 해도 시간초과는 나지 않는다.

 

코드

#include <string>
#include <vector>

/* (a>=b , a가 가로, b가 세로)
 * yellow : a*b 개
 * brown : 2a + 2b + 4 개
 */

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    for (int i = 1; i <= 2498; i++) {
        for (int j = i; j <= 2498; j++) {
            int br = 2 * i + 2 * j + 4;
            int ye = i * j;

            if (br == brown && ye == yellow) {
                answer.push_back(max(i + 2, j + 2));
                answer.push_back(min(i + 2, j + 2));
                return answer;
            }
        }
    }
}