문제 :
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] |
1 | 24 | [8,6] |
코드 :
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer(2); //초기화
int yellow_w;
for(int i=1;i<=yellow;i++){
if(yellow%i==0){
yellow_w=yellow/i;
if(i+yellow_w==-(brown-4)/2 || i+yellow_w==(brown-4)/2){
answer[0]=yellow_w+2; //w
answer[1]=i+2; //h
return answer;
}
}
}
}
다시 한번 짚고 넘어가기 :
-수학공식을 세워서 문제에 접근해보았다.
yellow의 width과 height를 중점적으로 식을 세웠다.
yellow_w*yellow_h=yellow이기 때문에
(yellow_w)*2 + (yellow / yellow_w )*2 =brown이고
yellow_w^2 -(brown-4)/2yellow_w+yellow=0이므로 11번째 줄의 if문이 나온것이다.
for문은 1부터 시작하기 때문에 i값은 yellow_w보다 작은 수이므로 answer[1]에 할당하였고 yellow의 w,h값이므로 +2를 하였다.
- 다른 답 :
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
int len = brown / 2 + 2;
int w = len - 3;
int h = 3;
while(w >= h){
if(w * h == (brown + yellow)) break;
w--;
h++;
}
return vector<int>{w, h};
}
카펫의 w와 h를 기준으로 세운식으로
w * h = brown + red, (w-2) * (h-2) = red, 두 식을 red를 대입해서 연립방정식을 이용한 풀이이다.
더 깔끔한 풀이인것 같다.
출처 : 프로그래머스 >다른 사람의 풀이
도움이 된 글 :
완전탐색의 종류를 알아보았다.
- 브루트 포스 : for문을 이용하여 처음부터 끝까지 탐색하는 방법
- 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT)
- 백트래킹 : 분할정복을 이용한 기법, 재귀함수를 이용, 해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
- 재귀함수 : 함수 내에서 함수 자기 자신을 계속해서 호출하는 것
- 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
- BFS(너비 우선 탐색)
- DFS(깊이 우선 탐색)
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스/level2/c++] H-index-"정렬" (0) | 2021.01.22 |
---|---|
[프로그래머스/level2/c++] 쿼드압축 후 개수 세기 (0) | 2021.01.22 |
[프로그래머스/level2/c++] 땅따먹기 (0) | 2021.01.20 |
[프로그래머스/level2/c++] 이진 변환 반복하기 (0) | 2021.01.19 |
[프로그래머스/level1/c++] 다트게임 (0) | 2021.01.19 |