[프로그래머스 42842 파이썬] 카펫 (level 2, 완전탐색)

알고리즘 유형 : 완전탐색
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import math

def solution(brown, yellow):
    answer = []
    # rule1 : w + b = brown/2 + 2
    # 2w + 2b - 4 = brown에서 도출된 조건 식
    # brown은 가로 줄 두개, 세로 줄 두개에서 겹친 4개 뺀 값
    rule1 = (brown // 2) + 2
    w = math.ceil(rule1 / 2)
    
    while w < rule1:
        h = rule1 - w
        # 노랑 격자의 총 가로 길이는 전체에서 -2
        # 세로도 마찬기지. 즉 총 노랑 격자 개수는
        # w-2 곱하기 h-2
        check = (w-2) * (h-2)
        
        if check == yellow:
            answer = [w, h]
            break
        
        w += 1
    
    return answer

소스 코드(javascript)

function solution(brown, yellow) {
    let answer = [];
    // rule1 : w + b = brown/2 + 2
    // 2w + 2b - 4 = brown에서 도출된 조건 식
    // brown은 가로 줄 두개, 세로 줄 두개에서 겹친 4개 뺀 값
    const rule1 = Number(brown / 2) + 2;
    let w = Math.ceil(rule1 / 2);
    
    while (w < rule1){
        const h = rule1 - w;
        // 노랑 격자의 총 가로 길이는 전체에서 -2
        // 세로도 마찬기지. 즉 총 노랑 격자 개수는
        // w-2 곱하기 h-2
        const check = (w-2) * (h-2);
        
        if (check === yellow){
            answer = [w, h];
            break;
        }
        
        w += 1;
    }
    
    return answer;
}

풀이 요약

1. w와 h를 미지수로 두고 조건 식을 구한 다음, 그 것을 만족하는 w와 h를 완전탐색하면된다. 문제에서 가로 길이가 반드시 세로 길이 이상이라고 했으므로 답은 유일하다.

2. 우선 2w + 2b - 4 = brown라는 식을 생각해볼 수 있다. 테두리 갈색 격자의 개수는 가로 두번, 세로 두번에 가로세로 겹치는 부분 4개를 빼준 값이다.

   이 식에서 w + b = brown/2 + 2가 나오고, 이를 만족하는 (w, b) 쌍을 완전탐색하면된다.

3. 이 때, 첫 번째 조건 식을 만족하는 (w, h) 쌍에 대해, 이 것이 정답인지 판별하는 조건 식을 하나 더 구할 수 있는데,

   노랑 격자의 개수로 식을 세우면 된다. 노랑 격자의 총 가로 길이는 전체에서 테두리에 해당하는 가로 길이를 뺀 w-2 이고, 세로도 마찬가지로 h-2이다. 즉, 노랑 격자의 총 개수는 (w-2) * (h-2)이다.

   (w-2) * (h-2) = yellow

   저 식을 만족하는 (w, h)쌍을 완전탐색하면 된다.

   유의할 점은, 가로 길이가 세로 길이 이상이여야 하므로, 탐색 출발 시 가로 길이는 가로+세로의 절반 이상이면된다. 이 후, 세로 길이가 1이 될때까지, 즉 가로 길이가 rule1 미만인동안 탐색하면 된다.

배운 점, 어려웠던 점

• 간단한 수학 식을 세워 활용하는 재밌는 완전탐색 문제였다.