카펫
문제 설명
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] |
시작 코드
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
return answer;
}
나의 풀이
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow)
{
int halfBrown = brown / 2; // halfBrown -> 행+열-2 의 길이
for(int i = halfBrown-1; i >= 3; i--)
{
int col = i, row = halfBrown - i;
// (행 - 2) * 열 -> 내부에 들어가는 yellow의 개수
if ((col - 2) * row == yellow)
{
return {col, row + 2};
}
}
return {};
}
코드 분석
brown을 2로 나눈 halfBrown값을 만들어 저장합니다. for문의 시작위치인 i를 halfBrown에서 1을 뺀 값으로 하고, i가 3보다 크거나 같아질 때까지 감소시키며 반복문을 실행합니다. 반복문 안에서는 col을 i로, row를 halfBrown에서 i를 뺀 값으로 만들고 if문에서 col에서 2를 뺀 값에 row를 곱한 값이 yellow와 같다면 col값과 row에 2를 더한 값을 리턴하도록 합니다. 만약 조건에 만족하지 않는다면 빈 벡터를 반환합니다.
풀이 설명
문제에서 요구하는 것은 카펫의 가로세로 크기입니다. 일단 문제에서 제시한 것과 같이 노란색은 중앙에, 바깥에는 갈색이 칠해져있다는 조건이 걸려 있습니다. 그리고 제한 조건에 카펫의 가로 길이는 세로와 크거나 같다고 적혀있습니다. 한마디로 위 그림과 같이 생겼지만 격자의 갯수는 매개변수로 주어져서 그 수만 달라진다고 생각하면 됩니다,
입출력 예 1번을 통해 실행시켜 보겠습니다. brown이 10, yellow가 2가 들어왔으니 halfBrown은 5가 됩니다. 반복문은 4부터 시작하여 3까지 돌아갑니다. 첫 시행을 돌리면 col(행)은 4, row(열)은 1이 되고 if문에서 계산을 진행하면 4 - 2 * 1 = 2가 만족하기 때문에 현재 col과 row에 2를 더한 값을 리턴하면 {4, 3}이 리턴되며 종료됩니다.
이 코드는 갈색 타일을 통해 가능한 가로와 세로의 조합을 계산하고, 내부 노란색 타일의 개수가 조건에 맞는지 확인합니다. 수학적 식에 의하면 brown = 2 × (가로 + 세로) − 4,
<NEXT>
오늘은 정답률 72%의 완전탐색 카테고리 문제 "카펫"을 풀어보았습니다. 다음에는 연습문제 "N개의 최소공배수" 문제를 다뤄보도록 하겠습니다. 감사합니다.
'프로그래머스 코딩테스트 문제 > Level 2' 카테고리의 다른 글
[프로그래머스] - 점프와 순간이동(C++) (0) | 2024.12.13 |
---|---|
[프로그래머스] - N개의 최소공배수(C++) (1) | 2024.12.08 |
[프로그래머스] - 짝지어 제거하기(C++) (0) | 2024.11.27 |
[프로그래머스] - 피보나치 수(C++) (2) | 2024.11.26 |
[프로그래머스] - 다음 큰 숫자(C++) (0) | 2024.11.25 |