구름LEVEL
구름LEVEL 문제를 풀이하고 부족한 부분을 보완하며 실력을 키워보세요. 구름LEVEL은 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입
level.goorm.io
풀이
그리디 알고리즘 활용
1. 직사각형을 만들기 위해서 필요한 막대는 4개
2. 같은 길이의 막대 2개를 한 세트로, 두 세트가 필요
3. 같은 길이의 막대가 4개 이상이면 정사각형 만들기 가능
!! 길이가 긴 막대부터 차례로 직사각형을 만들어 나가는 것이 만들 수 있는 직사각형 넓이의 합의 최대값 !!
처음엔 map에 key값에 막대 길이, value값에 막대 개수를 저장하고 iterator로 탐색하며 사각형을 구현하도록 코드를 작성했는데, Time out 발생
>>
입력값의 최대 크기인 10의 6승만큼 크기를 가진 input 배열을 선언하고 해당 배열의 인덱스를 막대기의 길이로, 인덱스의 값을 막대기의 개수로 대입하여 사용
** input 배열을 전역변수로 선언하여 Time out 방지
input 배열 뒤부터 길이가 긴 순으로 탐색
막대가 2개 이상이라면 킵하고
그 이후에 2개 이상 막대가 발견되면 이전의 막대와 직사각형을 만들어 넓이 계산 후 answer에 더함
-- 반복
long long input[1000000] = { 0, }; // 막대 길이와 막대 개수 정보를 담을 배열 전역변수 선언
// index : 막대 길이
// input[index] : index 길이의 막대 개수
int main() {
int n; // 입력값
cin >> n;
long long answer = 0;
bool flag = true; // 개수가 2 이상인 막대가 선택됬을 때, 이전에 이미 선택 된 막대가 있는지 판단하는 변수
int curVal = 0;
// 반복문으로 input에 막대 개수 정보 입력
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
input[temp]++;
}
// 길이가 긴 순으로 탐색
for (long long i = 1000000; i > 0; i--) {
// 만약 막대의 개수가 2개 이상이고
if (input[i] >= 2) {
// 이전에 선택된 막대가 없다면
if (flag) {
curVal = i; // curVal에 막대의 길이 저장
flag = false;
}
// 이전에 선택된 막대가 있다면
else {
answer = answer+ (curVal * i); // 이전에 선택된 막대와 현재 막대를 곱해서 넓이 계산
flag = true;
}
input[i] -= 2; // 막대의 개수 2개 감소
i++; // 예를 들어 현재 막대가 4개일 경우 같은 길이의 막대를 4개 사용하여 사각형을 만들 수 있기 때문에 현재 막대를 한 번 더 탐색하기 위한 i값 1 증가
}
}
cout << answer << endl;
}'코딩테스트 > 문제풀이' 카테고리의 다른 글
| [백준] 계단 오르기 Java (0) | 2023.08.29 |
|---|---|
| [백준] 가운데를 말해요 Java (0) | 2023.07.17 |
| [구름] 어부의 고기잡이 C++ (0) | 2023.07.10 |
| [구름] 단풍나무 C++ (0) | 2023.07.10 |
| [구름] 뒤통수가 따가워 C++ (0) | 2023.07.07 |