[코딩테스트] 최대한 많은 사각형 만들기

요구사항

길이가 1인 n개의 막대기가 주어질 때 바닥에 막대기를 놓아 1*1 짜리 정사각형을 만드려고 한다.

이때 만들 수 있는 사각형의 최대 갯수 구하기

 

 

예시

1. 막대기가 5개 주어지는 경우, 막대기 하나를 남기고 4개로 정사각형 하나를 만들 수 있다.

 

2. 막대기가 10개 주어지는 경우, 처음 4개로 정사각형을 만들고 3개를 이어붙여 두번째 정사각형

    또 3개를 이어붙여 세번째 정사각형을 만들 수 있다.

 

3. 막대기가 12개 주어지는 경우, 아래 그림과 같이 배치하면 정사각형을 최대 4개 만들 수 있다.

 

 

입력 값

int stick

막대기 갯수 (n>4)

 

 

풀이

1. 초기 박스 1개 생성

    -> 막대기 갯수에서 4개 차감

    -> 현재 박스수, 가로길이, 세로길이 1로 초기화

 

2. 박스 이어 붙이기

    -> 가로길이와 세로길이가 동일하고 박스로 정사각형을 모두 채웠을(가로길이*세로길이 == 박스수) 때

        가로에 한칸 추가하고 막대기 3개 차감하여 이어붙이기

    -> 가로길이가 세로길이보다 길고 박스로 직사각형을 모두 채웠을(가로길이*세로길이 == 박스수) 때

        세로에 한칸 추가하고 막대기 3개 차감하여 이어붙이기

    -> 그 외의 경우는 막대기 2개로 이어붙일 수 있음

 

3. 남은 막대기로 더이상 이어붙일 수 없을 때까지 2번 반복

 

4. 만들어진 정사각형 갯수 return 

 

728x90

Java 코드

class Solution {
    public long solution(int stick) {
        long answer = 0;
        
        // 초기 박스
        stick -= 4;
        int boxCnt	= 1;
        int width	= 1;
        int height	= 1;

        while(stick > 0) {
            if(width == height && width*height == boxCnt ) {
                stick-=3;
                width++;
            } else if(width > height && width*height == boxCnt) {
                stick-=3;
                height++;
            } else {
                stick-=2;
            }
            if(stick < 0) break;
            
            boxCnt++;
        }

        answer = boxCnt;
        
        return answer;
    }
}