반응형
입력 & 출력
가로의 길이 W와 세로의 길이 H가 주어질 때,
사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
풀이
두 방법을 생각했다
하나는 사각형을 더 만들어 규칙이 존재하는지 찾아보는 것이고
다른 하나는 비율에 따른 삭제되는 사각형의 개수를 찾는 것이다
전자의 방법으로 풀어보자
4, 4 사각형의 경우 4 개가 빠진다
2, 3 사각형인 경우 4 개가 빠진다
9, 3 사각형의 경우 9 개가 빠진다
한 눈에 봐서는 규칙을 찾기 힘들다..
삽질을 하며 찾아보았는데 최대 공약수를 구하고 사칙연산을 하니 한 규칙을 찾게 되었다
w과 h의 최대 공약수를 구해 w + h 에서 빼주면 삭제되는 수를 구할 수 있었다
남아있는 사각형의 개수는 w * h - (w + h - g) 식을 따른다
Swift 전체 코드
func solution(_ w:Int, _ h:Int) -> Int64 {
func gcd(_ a : Int, _ b : Int) -> Int{
if a % b == 0 {
return b
}
return gcd(b, a % b)
}
return Int64(w * h - (w + h - gcd(w,h)))
}
반응형
'개발 > 알고리즘' 카테고리의 다른 글
[프로그래머스] 스킬트리 (0) | 2021.04.01 |
---|---|
[프로그래머스] 스택/큐 - 기능개발 (0) | 2021.04.01 |
[프로그래머스] DFS / BFS - 네트워크 (0) | 2021.04.01 |
[프로그래머스] DFS / BFS - 타켓 넘버 (0) | 2021.04.01 |
[프로그래머스] 완전탐색 - 모의고사 (0) | 2021.03.31 |