[ 알고리즘 / kotlin ] 프로그래머스 lv2 멀쩡한 사각형

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ

이번엔 프로그래머스 level 2에 있는 멀쩡한 사각형에 대해 풀어보려고 합니다.

 

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

프로그래머스

코드 먼저 보여드리겠습니다.

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun solution(w: Int, h: Int): Long {
    val lw = w.toLong()
    val lh = h.toLong()

    var answer: Long = (lw * lh)


    return answer - (lw+lh- gcd(lw,lh))
    }
}
fun gcd(a: Long, b: Long): Long {
    var maximum = max(a, b)
    var minimum = min(a, b)

    if (minimum == 0.toLong()) {
        return max(a, b)
    } else {
        return gcd(minimum, maximum % minimum)
    }
}

 

위의 gcd 함수는 최대공약수를 리턴해주는 함수입니다.

이 함수에 대한 설명은 아래 링크를 타고 들어가셔서 보시면 되겠습니다~ (봐주세요 ㅠ)

2020/04/29 - [알고리즘] - [ 알고리즘 / kotlin ] 최대공약수 구하기 - 유클리드 호제법

 

처음 문제를 접했을 때 뭔가 규칙이 있을꺼같아서 여러가지 경우를 생각을 했습니다.

처음으로 시도한 것은 대각선에 걸쳐져 있는 사각형들의 인덱스 별로 탐색을 하는것이였습니다.

goX = {1,1,0,1}

goY = {0,1,0,1} 요런식으로 배열에 넣은 다음 

마치 dfs문제를 풀듯이 접근을 했는데 결과는 참담했습니다.( 실행 테스트는 맞았지만 전체 테스트에서는 0점 하하!)

 

그 후 몇 시간을 더 고민 끝에!!!! 구글링을 하기로 했습니다 ㅎ;

 

정말 엄청나게 똑똑하신 분들이 많더라구요 항상 느낍니다 ㅠㅠㅠ

참고한 블로그를 소개하자면

https://taesan94.tistory.com/55

여깁니당 

 

암튼 최대공약수를 이용하여 푸는 방법이였는데 신기하더라구요 ㅎ

다음 번에도 이런 유형의 문제가 나온다면 제 머릿속의 경우에 최대공약수를 쓰는 방법도 추가를 해서 

풀어봐야겠네요 

 

위에 소개한 블로그에 더 자세하게 설명이 나와있으니 코드로만 부족하신 분들은 위 블로그에 가셔서 보시면 될 것 같습니다. 

저는 설명을 잘 못 하겠더라구요 ㅠ_ㅠ

 

 

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!