[프로그래머스] K번째 수

https://programmers.co.kr/learn/courses/30/lessons/42748

문제

문제

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

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

풀이

먼저 노란색 부분을 항상 한줄의 갈색 격자가 둘러싸고 있기 때문에, 가로열의 길이는 절대 노란색 격자수 + 2 를 넘어설 수 없다. 노란색 격자를 일렬로 쭉 늘어놓는 것보다 더 길게 노란색 격자를 둘 수 있는 방법이 없기 때문이다.

또한, 문제에서 가로크기가 항상 세로 크기보다 같거나 크다고 주어졌기 때문에 아래와 같이 반복문을 구성할 수 있다.

for (int col = 3; col <= yellow + 2; col++) {
    for (int row = 3; row <= col; row++) {
    }
}

그럼 이제 반복문으로 모든 가로세로 길이를 조합해보면서 카펫을 만들 수 있는지 확인해보면 된다. 카펫을 만들 수 있는 조건은 두 가지이다.

1. (세로 길이 - 2) * (가로길이 - 2) 는 노란색 격자의 개수와 같아야 한다. 테두리를 제외한 카펫의 크기이기 때문이다.
2. 세로 길이 * 가로 길이 는 카펫의 전체 격자 수와 같아야 한다.

이 두 가지 조건을 만족하는 가로X세로 조합을 발견하면 곧바로 정답으로 반환한다.

코드

{% raw %}
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int brown, int yellow) {
    for (int col = 3; col <= yellow + 2; col++) {
        for (int row = 3; row <= col; row++) {
            if ((col - 2) * (row - 2) == yellow
                && col * row == brown + yellow) {
                return { col, row };
            }
        }
    }
}
{% endraw %}