쌓고 쌓다
[프로그래머스] 카펫 C++ 풀이 본문
https://school.programmers.co.kr/learn/courses/30/lessons/42842
전체 코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
for(int i=3;;i++) //세로
{
for(int j=3;;j++) //가로
{
if(i*j>brown+yellow)
break;
else if((i-2)*(j-2)==yellow)
{
answer.push_back(j);
answer.push_back(i);
return answer;
}
}
}
}
풀이 방법
3x3을 예로 들어보겠다.
Yellow 부분은 겉 테두리를 제외하고 꽉 채운다.
즉, 맨위 1칸과 맨아래 1칸을 빼버린것이 yellow 구역의 세로 길이가 된다.
이것은 가로 길이도 똑같이 적용된다.
그럼 이 원리는 4x3이든 4x4이든 동일하게 적용이 된다.
테두리만 제외하면 yellow 구역이 되니깐 전체 길이에서 맨위, 맨아래 즉, 양 사이드 블럭 2개를 빼버리면 yellow 구역의
한쪽 길이를 구할 수 있는것이다.
이런 방식으로 세로 길이와 가로 길이가 주어졌을때 우리는 yellow 구역의 넓이를 구할 수 있다.
그래서 yellow 구역의 넓이가 일치하는 카펫의 모양을 찾는것이 해법이다.
for(int i=3;;i++) //세로
{
for(int j=3;;j++) //가로
{
...
}
}
for문은 세로와 가로 길이를 모두 탐색하게 만들었다.
i와 j가 3부터 시작인 이유는
문제 조건에서 brown은 8이상, yellow는 1이상이 최소값이므로
만족하는 최소크기의 카펫모양은 3x3이다.
그래서 가로 세로 길이를 3부터 시작한것이다.
if(i*j>brown+yellow)
break;
카펫의 넓이는 brown+yellow를 넘어 설 수 없으니
이때 break하여 가로 길이의 반복문을 탈출하게 만들었다.
else if((i-2)*(j-2)==yellow)
{ ... }
세로 길이 i에서 2를 뺀 길이와 가로 길이 j에서 2를 뺸 길이를 곱하면
yellow 구역의 넓이가 되는데 이것이 yellow와 일치하면
찾던 카펫 모양을 찾은것이다.
yellow만 가지고 주어진 brown과 yellow를 만족시키는 카펫의 모양을 찾을 수 있을까 싶은데
찾을 수 있다. 그냥이 아니고 아래의 if문 덕분이다.
if(i*j>brown+yellow)
break;
yellow가 24개인 카펫을 찾으려고 하는데 카펫의 모양은 여러개가 있다.
그중 두개만 들면
이런 모양인데 두개다 (i-2)(j-2)==yellow를 만족한다.
하지만 우리에게 주어진 yellow, brwon 블럭의 개수의 합은 i*j를 넘어갈 수 없기에
위의 if문에서 다 걸러져 만들 수 있는 사각형만 걸러져 나온다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 구명보트 C++ 풀이 (0) | 2022.10.11 |
---|---|
[프로그래머스] 영어 끝말잇기 C++ 풀이 (0) | 2022.10.09 |
[프로그래머스] 다음 큰 숫자 C++ 풀이 (0) | 2022.10.06 |
[프로그래머스] 피보나치 수 C++ 풀이 (0) | 2022.10.03 |
[프로그래머스] 숫자의 표현 C++ 풀이 (0) | 2022.09.30 |