[백준] 거북이

■ 문제

 

  거북이는 이제 어떤 것에도 흥미를 느끼지 않는다. 그 이유는 거북이가 300년동안 살았고, 그 동안 모든 것들을 다 해보았기 때문이다. 거북이는 시간을 떼우는 무엇인가를 하려고 한다. 이번 주말에 거북이는 거북이 세계에서 매우 유명한 게임인 "가장 큰 직사각형 만들기"를 해보려고 한다.

 

 이 게임을 시작하기 전에 거북이는 양의 정수 네 개를 머릿 속에 생각해야 한다. 한 방향으로 움직이기 시작하고 90도 회전한 뒤에 새로운 방향으로 움직인다. 이런 식으로 세 번 90도 회전을 하고, 네 번 앞으로 움직여서 선 분 네 개를 만들어야 한다.

 

 거북이가 선분을 그릴 때 움직여야 하는 걸음의 수는 생각해 놓은 네 정수중 하나이다. 이때, 한 정수를 각각 한 번씩 사용해야 한다. 거북이가 정수를 사용하는 순서에 따라서 다양한 모양이 만들어진다. 어떤 모양은 직사각형을 만들 수 없기도 한다.

 

 거북이가 만들 수 있는 가장 큰 직사각형을 계산하는 프로그램을 작성하시오.

 

■ 입력

  첫째 줄에 거북이가 생각한 네 양의 정수 A, B, C, D가 주어진다. (0 < A, B, C, D < 100)

 

■ 출력

  첫째 줄에 거북이가 만들 수 있는 가장 큰 직사각형의 면적을 출력한다.

 

■ 예제

입력	출력
1 2 3 4	3

▶ 내가 푼 코드

 

문제를 풀기 전 기본적인 컨셉은 다음과 같았다.

 

1. 사각형이 되는 경우의 모든 경우의 수를 찾는다. => DFS
2. 사각형이 되는 경우에만 넓이를 계산해 vector에 삽입한다.
3. sort 함수로 정렬 후 가장 큰 경우를 출력한다.

1번, 사각형이 되는 경우의 모든 경우의 수를 찾는 곳을 자세히 보자.

 

우선 사각형을 만들 때, rect 배열에 [1, 2, 3, 4]라는 경우의 수가 만들어 졌다면

왼쪽부터 사각형의 왼쪽, 상단, 오른쪽, 하단을 구성한다고 생각해보자.

 

위 경우에는 사각형을 만들 수 없다.

사각형을 만들기 위해서는 rect[0] >= rect[2] 하고 동시에 rect[1] <= rect[3]을 만족해야한다.

 

이 경우에만 사각형을 만들 수 있으므로 사각형의 넓이를 저장하는 rect_area에 사각형의 넓이를 계산하여 삽입한다.

 

전체 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[4];
bool visit[4] ={false};
int rect[4];
vector<int> rect_area;

void dfs(int n) {

    if(n==4){
        /* 2. 사각형이 되는 경우에만 삽입*/
        if(rect[0]>=rect[2] && rect[1]<= rect[3]){
            rect_area.push_back(rect[1] * rect[2]);
        }
    }else{
        for(int i=0; i<4 ; i++){
            if(!visit[i]){
                visit[i] = true;
                rect[n] = arr[i];
                dfs(n+1);
                visit[i] = false;	
            }
        }
    }
}

int main(){
	
    for(int i=0;i<4;i++)
        cin >> arr[i];
	
    /*1.사각형이 되는 경우의 수 찾기*/
    dfs(0);
	
    /*3.정렬 후 가장 큰 경우 출력*/
    sort(rect_area.begin() , rect_area.end());
    cout << rect_area[rect_area.size()-1];
    
    return 0;
}

 

▶ 수정 후 코드

 

스터디원들과 코드를 공유하던 중 더 간결하게 짤 수 있는 방법이 있었다.

 

우선 이 문제의 경우 가장 넓은 사각형을 만들기 위해서 조건은 다음과 같다.

 

1. 가장 긴 변과 그 다음으로 긴 변이 마주보고 있어야한다.
2. 위 경우를 제외한 두 변이 마주보고 있어야한다.

예를들면 [1, 2, 3, 4]의 경우

 

1) 가장 긴 변(4)와 그 다음으로 긴 변(3)이 마주보고 있어야한다.

2) 위 경우를 제외한 (1),(2)가 마주보고 있어야한다.

 

1과 2에서 짧은 변을 곱한 것이 가장 큰 사각형의 넓이가 된다.

 

다음을 코드로 짜면 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> rect;

int main(){
	
	int n;
	
	for(int i=0;i<4;i++){
		cin >> n;
		rect.push_back(n);
	}
	
	sort(rect.begin() , rect.end());
	
	cout << rect[0] * rect[2];
    
	return 0;
}

 

 

※ 출처 : https://www.acmicpc.net/problem/2959

2959번: 거북이