카펫 - 수학적으로 풀었다고 생각한 풀이와 진짜 수학적 풀이

문제 이름 및 링크

카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

출제 사이트

프로그래머스

문제유형 및 난이도

문제유형: 완전탐색

난이도: 레벨2

코드 설명

아래의 코드는 제가 나름 수학적인 접근이라고 생각했던 풀이입니다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2]; // 순서대로 가로, 세로 크기를 담아야 함
        // yellow가 두 곱의 형태로 나타나는 조합을 찾는다.
        // ex) 24 => 2*12, 3*8, 4*6
        for(int i=1; i<=Math.sqrt(yellow); i++) {
            if(yellow%i==0) { // 가로가 세로 길이보다 길거나 같아야 한다.
                int width = (int) yellow/i;
                int length = i;
                // 나온 조합에서 좌항 우항에 2를 더한 값으로 곱 연산을 만든다.
                // ex) 2*12 => 4*14, 4*6 => 6*8
                int fullSize = (width+2)*(length+2);
                // 만약 2를 더한 값으로 만든 결과에서 yellow 개수를 뺐을 때, brown과 같은 값을 가진다면 반환한다.
                // ex) 6*8 - 24 = 24
                if(fullSize-yellow==brown) {
                    answer[0] = width+2;
                    answer[1] = length+2;
                }
            }
        }
        return answer;
    }
}

 

하지만 진짜 수학적 풀이는 이거였습니다.

import java.util.*;
class Solution {
    public int[] solution(int brown, int red) {
        int a = (brown+4)/2;
        int b = red+2*a-4;
        int[] answer = {(int)(a+Math.sqrt(a*a-4*b))/2,(int)(a-Math.sqrt(a*a-4*b))/2};
        return answer;
    }
}

 

방정식으로 풀이를 풀어내어 근의 공식을 쓰는 방식으로 푸는 방법은 생각도 못했습니다.

O(1)으로 줄인게 굉장히 인상적이었습니다.