티스토리 뷰
Leo가 길에서 본 카펫이 갈색 격자 테두리가 둘러져 있고 내용물은 노란색 격자로 채워져 있는데
Leo는 노란 격자 갯수와 갈색 격자 갯수만 기억하지만 카펫의 전체 크기는 기억하지 못한다.
이거만 해도 기억력이 많이 좋은거 같지만 Leo는 여기서 멈추지 않는다...
Leo가 길에서 본 카펫의 노란색과 갈색 격자의 갯수를 이용해서 카펫의 전체 크기를 구하고 싶어하는 문제
문제의 조건
1. 갈색 격자 갯수 brown, 노란 격자 갯수 yellow가 주어짐
2. 카펫의 테두리는 갈색 격자로 둘러져 있음
즉 카펫의 최소 높이는 3이다.
예시 그림과 같이 노란 격자를 최소 한 칸 포함하면서 갈색 격자로 테두리가 둘러지려면 최소 3칸이 필요하다.
-> 이렇게 접근했어야 하는데 처음에는 최대 너비를 구해서 접근하는 바람에 계산식만 괜히 복잡해지고 답은 나오지 않고 엄청 헤멨다.
4. 갈색과 노란 격자의 갯수가 주어지기 때문에 저것들을 모두 더하면 카펫의 넓이를 구할 수 있다.
전체 카펫의 넓이에서 최소 높이 3으로 나누면 카펫의 초기 너비값을 구할 수 있다.
이제 갈색 격자의 갯수를 구해야 하는데,
노란 격자는 카펫의 안쪽에 연속해서 채워져있기 때문에 노란 격자의 갯수는 노란 격자가 차지하는 넓이와 같다는 걸 알 수 있다.
그런데 카펫 전체의 너비 = 가로 방향으로 갈색 격자가 놓인 갯수, 높이 = 세로 방향으로 갈색 격자가 놓인 갯수이다.
즉 갈색 격자의 너비 = 노란 격자의 너비+2, 갈색 격자의 높이 = 노란 격자의 높이+2 라는 것을 알 수 있다.
그렇다는 것은 (카펫의 너비 - 2) * (카펫의 높이 - 2) 가 노란 격자의 갯수(넓이)와 같다면
실제 카펫의 너비와 높이를 구할 수 있게 된다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
int height = 3; //초기값은 최소 높이 3으로 설정
while (true)
{
int width = (brown + yellow) / height;
//(가로 - 2) * (세로 - 2) 가 yellow와 같으면 계산 끝~~
if (yellow == (width - 2) * (height - 2))
{
answer.emplace_back(width);
answer.emplace_back(height);
break;
}
else //if 조건에 맞지 않으면 높이를 1씩 높여가면서 가로길이를 구한다.
height++;
}
return answer;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[C++] 프로그래머스 단체사진 찍기 풀이 (0) | 2021.10.15 |
---|---|
[C++] 프로그래머스 오픈채팅방 풀이 (0) | 2021.10.14 |
[C++] 프로그래머스 소수 찾기 풀이 (0) | 2021.10.12 |
[C++] 프로그래머스 베스트앨범 풀이 (0) | 2021.10.12 |
[C++] 프로그래머스 문자열 압축 풀이 (0) | 2021.10.12 |
- Total
- Today
- Yesterday
- BFS
- 컴퓨터공부
- 아이패드
- 너비우선탐색
- 다이나믹프로그래밍
- c++
- 코딩공부
- 캐나다
- 프로그래밍
- 알고리즘
- 컴퓨터사이언스
- greedy
- DFS
- 프로그래머스
- 해커랭크
- 하드웨어
- 깊이우선탐색
- 문제풀이
- 그리디
- 컴퓨터
- c언어
- dp
- 기초
- 영어공부
- C언어기초
- 스위프트플레이그라운드
- 캐나다생활
- 애플
- 백준
- hackerrank
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |