[프로그래머스/Lv. 2] 카펫

🔺 문제

프로그래머스

 

 

🔺 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int sum = brown + yellow;
        
        for(int i = 3 ; i < sum ; i++) {
            int width = sum / i;    // 가로
            
            if(width >= i) {
                if((i - 2) * (width - 2) == yellow) {
                    answer[0] = width;  // 가로
                    answer[1] = i;      // 세로
                    break;
                }
            }
        }
        return answer;
    }
}

• 세로 ➡  3 이상 (노란색 격자수가 1 이상이므로)

• 카펫 사이즈 경우의 수 ➡  (brown + yellow)의 약수 구하기

• yellow 갯수 ➡  (가로 - 2) * (세로 - 2)

 

 

풀이를 보고 나면 참 별게 아닌데(?) 나는 그 쉬워보이는 걸 못하고 있다... 답답하구만😶😶

---

🔺 다른 풀이들

[프로그래머스] 카펫 자바(JAVA)

 

 

 

---

(+ 2회독 231018)

 소인수분해를 활용했다.

 

yellow를 소인수분해해 나온 두 값 A와 B를 더하고 2를 곱하고, 꼭짓점 4개를 더해 sum의 갯수를 구한다.

이 때 sum의 갯수가 brown의 값보다 (작거나) 같다면,

카펫의 가로의 길이는 두 소인수 분해한 값 중 큰 값 + 2, 세로의 길이는 두 소인수 분해 한 값 중 작은 값 +2가 된다.

 

import java.util.*;
 
class Solution {    
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        // 소인수분해
        for(int i = yellow ; i >= 1 ; i--) {
            if(yellow % i == 0) {                
                int sum = (i + yellow / i) * 2 + 4;
                if(sum <= brown) {
                    answer[0] = Math.max(i + 2, yellow/i + 2);
                    answer[1] = Math.min(i + 2, yellow/i + 2);
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

 

 

 

(+ 3회독 240711)

1) (가로 + 세로) = (brown - 꼭짓점 4개의 값)

2) 가로 * 세로 = yellow

 

이 두 식을 만족하는 x와 y를 찾고자 2중 for문을 활용한 완전탐색을 진행했다.... (비효율적)

import java.util.*;
 
class Solution {
    public int[] solution(int brown, int yellow) {        
        int[] answer = new int[2];
        
        for(int i = 1 ; i <= brown ; i++) {
            for(int j = 1 ; j <= yellow ; j++) {
                if(2 * i + 2 * j == (brown - 4) && (i * j == yellow)) {
                    if(i >= j) {
                        answer[0] = i+2;
                        answer[1] = j+2;
                        break;
                    }
                }
            }
        }
        
        return answer;
    }
}

 

---

(참고)

[Java 자바] 프로그래머스 > Lv.2 카펫