프로그래머스 카펫

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

프로그래머스

 

문제 설명

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,

전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로,

세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown yellow return

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

---

 

나는 이렇게 문제에 그림이 있으면 너무 좋더라…

뭔가 직관적이고 풀고 싶게 생긴 느낌이랄까?

이 문제를 처음 보고 어떻게 접근해야 할지 고민을 했는데. 완전탐색이라 경우의 수를 다 따져가며 떄려 맞추는 식으로 풀기로 했다. 물론 시간 제한도 고려하면서…

우선 문제를 풀기 전에 패턴을 확인했다. 갈색 타일과 노란색 타일의 관계를 생각해 가며 알고리즘을 구현했다. 결국 리턴 값은 노란색 타일을 감싸고 있는 갈색 타일의 가로 세로 개수이기 때문이다.

갈색의 가로와 세로는 항상 노란색 가로 세로의 +2만 해주면 되고, 관계를 유지한 상태에서 두개 색깔의 타일 개수 합과 같으면 값을 반환하면 된다.

 

 

알고리즘

1. 먼저 갈색과 노랜색 타일의 합을 저장하는 sum변수를 선언한다.
2. 이중 배열을 사용했고, 넉넉하게 sum만큼 돌려주기로 한다.
3. 첫번째 조건은 가로*새로가 노란색 타일의 개수와 같고, 가로가 더 큰 경우를 만족하는가이다.
4. 조건이 참인 경우 둘러싸고 있는 갈색 타일의 개수를 구하고 노란색 타일과 더했을 경우 전체 타일 수와 동일한지 판단하는 조건문이다.
5. 둘 다 만족하는 경우 백터에 push해주고, 값을 반환하고 종료해준다.

 

 

코드

#include <string>
#include <vector>
#include <math.h>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    int sum=brown+yellow;
    
    for(int i=1; i<=sum; i++){
        for(int j=1; j<=sum;j++){
            if(i*j==yellow && i<=j){
                if(((j+2)*2+i*2)+yellow==sum){
                    answer.push_back(j+2);
                    answer.push_back(i+2);
                    return answer;
                }
            }      
        }
    } 
    return answer;
}

 

 

4,6,7번 케이스 통과 못하는 경수를

이렇게 테스트 케이스를 추가해서 돌려보면 실패라고 뜰 것이다.

[18, 6] -> [8, 3] (o)

[18, 6] -> [6, 4] (x)

저 위에 두 배열들은 약수가 맞으나,

차이점은 8, 3 의 경우에는 안에 채워지는 갯수가 yellow와 동일하지만,

6, 4 의 경우에는 안에 채워지는 갯수가 yellow 보다 크다.

이러한 예외 케이스도 고려해서 풀어보심이 좋다.