프로그래머스 Level 2 카펫

출처: 프로그래머스

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

프로그래머스

 

카펫 문제

 

풀이

 

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        var width = 3
        var height = 3
        while (width >= height) {
            val y = (width - 2) * (height - 2)
            val b = width * height - y
            if (y == yellow && b == brown) break
            if(y<yellow && b == brown) {
                width--
                height++
            } else width++
        }
        return intArrayOf(width, height)
    }
}

 

해설 

 

기본 3x3 정사각에서 출발한다고 가정합니다.

가로 변수는 width = 3

세로 변수는 height  = 3

구해야 하는 것은 무엇일까요?? => yellow와 brown을 가지고 카펫의 가로 세로를 구해야 합니다.

다만 yellow는 안에 사각형 brown은 테두리 사각형의 개수입니다.

 

위와 같은 그림에서 가운데 개수는 1개 테두리 8개입니다.

 

위와 같은 4x3에서 사각형은 가운데 사각형의 개수는 가로 2(4-2) x 세로 1(3-2)로 2개입니다.

 

즉 가로 세로 값에서 -2 한 값이 안에 있는 사각형의 가로 세로 길이입니다.

가로 세로 곱을 하면 yellow 사각형의 개수가 나오고 

width와 height를 곱한 전체에서 yellow의 값을 빼주면 brown 값이 나오게 됩니다.

이를 이용하여 yellow 개수와 brown 개수를 구합니다.

 

구해야 하는 건 yellow와 brown이 주어질 때 가로 세로입니다.

가로 세로가 특정 값일 때 yellow brown을 구할 수 있으니 

가로 세로 값을 하나씩 올리면서 그때의 yellow 값과 brown 값을 비교해 답을 찾습니다.

 

그렇다면 어떻게 가로 width 값과 height 값을 올려야 할까요?

먼저 가로를 전부 올려봅니다. 

while 문 안에 if else문을 보면

( 변경사항 => ( y<yellow && b == brown ) 로 변경합니다. 저렇게 해도 되지만 큰 경우는 나오지 않습니다. )

방식은 오른쪽으로 먼저 끝까지 증가시키게 됩니다.

if문의 조건은 brown의 개수는 같지만 y가 부족할 때는 가로를 한 칸 줄이고 세로를 한 칸 늘립니다.

b 값은 현재 width, height에서의 brown의 개수 값입니다.

else 문에서는 y값과 b값이 둘 다 yellow, brown 값보다 작을 경우를 따집니다.

둘 다 작다면 가로를 계속 늘립니다. 가로가 계속 늘어가 입력받은 brown 값이 나오게 되면 그때부터는 가로 값을 하나씩 줄이면서 세로를 늘려줍니다.

가로가 먼저 만족하는 경우를 찾고 그 이후부터 세로를 하나씩 줄여나간다 입니다.

가로를 하나씩 줄이면서 세로를 늘리면 가로의 값은 계속 같은 가로 값을 갖게 됩니다.

왜냐하면 가로를 먼저 만족시키고 가로-- , 세로++ 하면 

가로를 한 번 줄일때 -2개가 줄고 세로를 늘리면 +2 가 되어 값을 유지하게 됩니다.

그러므로 가로를 먼저 찾고 가로를 줄이고 세로를 늘려가면서 yellow 값을 찾을 수 있습니다.

 

아래의 그림에서 가로는 현재 11입니다. 

11일 때 b 값은 24입니다.

이때부터 가로는 줄이고 세로를 늘립니다.

 

현재 가로 10 세로 4입니다. y는 16, b는 24입니다.

다시 가로 감소 세로 증가합니다.

 

 

위의 그림에서 아래처럼 다시 바뀌게 됩니다.

y는 7x3 21입니다. b는 45(9x5)-21(y)= 24입니다.

 

 

 

한 번 더 세로를 늘리고 가로를 줄이겠습니다.

 

가로 8 세로 6입니다.

y = 6x4 = 24입니다.

b = 48-24입니다. 

둘이 개수가 같으므로 while 문을 탈출하고 답을 구합니다.

 

 

이상으로 카펫 문제의 풀이를 마치겠습니다. 감사합니다.