[고득점 Kit (완전탐색)] 카펫 (swift)

코딩테스트 연습 - 카펫

 

 

풀이

---

먼저 갈색 격자의 수에서 모서리에 있는 4개를 제거해준다.

 

 

(갈색 격자의 수 - 4)는 (노란색 격자의 가로 길이 * 2) + (노란색 격자의 세로 길이 * 2)가 된다.

 

그럼 이제 for문을 돌면서 노란색 격자의 가로 길이와 세로 길이를 구한다. 문제에서 카펫의 가로 길이가 세로 길이보다 길거나 같다고 했으므로 항상 가로 길이 > 세로 길이임을 알 수 있다. 위의 그림은 노란색 격자가 총 24개 있는 상태다. for문을 돌 때 노란색 격자 개수의 제곱근까지만 돌아주면 모든 경우를 다 살펴볼 수 있다.

그렇게 가로 길이와 세로 길이를 구해놓고 위의 식처럼 해줬을 때 (갈색 격자의 수 - 4)와 같다면 이를 결과 배열에 담아주고 탐색을 종료한다.

 

코드

---

 

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    let brownCnt: Int = brown - 4 // 대각선의 각 끝 방향 4개 제거
    var height: Int = 0 // 세로
    var width: Int = 0  // 가로 (가로가 항상 세로보다 길거나 같다)
    var res: [Int] = [0, 0]
    
    for i in 1...Int(sqrt(Double(yellow))) {
        if yellow % i != 0 {
            continue
        }
        
        height = i
        width = yellow / i
        
        if height*2 + width*2 == brownCnt {
            res[0] = width + 2
            res[1] = height + 2
            break
        }
    }
    
    return res
}