250x250
06-26 09:54
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 프로그래머스 멀쩡한 사각형 -Summer/Winter Coding(2019)- 본문

알고리즘/수리

[알고리즘] 프로그래머스 멀쩡한 사각형 -Summer/Winter Coding(2019)-

막무가내막내 2020. 4. 6. 20:50
300x250
SMALL

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

프로그래머스 멀쩡한 사각형이라는 문제를 풀어봤습니다.

30분 정도 풀다가 사각형에서 자도 없어서 대각선 그려서 사각형 몇개 지나는지 그리거나 보기도 힘들고 기울기 방정식이나 분할해서 계산, 규칙 등 계속 볼려고 했으나 모르겠어서 바로 구글링했습니다. 허허

출처: https://m.blog.naver.com/PostView.nhn?blogId=zzinuhelios&logNo=120024685950&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

그렇답니다. 설명은 사이트 들어가면 자세히 나와있습니다. 공식을 아니 최대공약수만 구할 줄 알면 바로 풀리는 문제였습니다. 

 

이번 문제로 얻어간 거는 저러한 공식이 있다는거와 최대공약수 구하는 방법이였던 것 같습니다.

 

풀이는 다음과 같습니다.

class Solution {
    //대각선이 지나는 단위정사각형'에 대한 문제 중 직사각형의 각 변을 m,n이라고 할때 공식은 m+n-(m과n의 최대공약수)입니다.
    public long solution(long w, long h) {
        long answer = 1;
        long GCD = 1;
        if (w > h) {
            GCD = gcd(w, h);
        } else {
            GCD = gcd(h, w);
        }
        long passSquare = w + h - GCD;
        answer = w * h - passSquare;
        return answer;
    }

    public static long gcd(long big, long small) {
        if (big % small == 0) {
            return small;
        }
        return gcd(small, big % small);
    }
}

 

 

 

추가로 최소공약수도 알아봤습니다. 최대공약수에대해서도 써있습니다. 바로 써먹을 수 있게 외워놉시다.

출처: https://ggmouse.tistory.com/317

 

[JAVA] 백준 알고리즘 2609 : 최대공약수와 최소공배수

문제 소스 import java.util.Scanner; public class Main { // 최대공약수 (Greatest Common Divisor) public static int gcd(int x, int y) { // 유클리드 (x를 y로 나눈 나머지가 0보다 클때까지 반복) while(y..

ggmouse.tistory.com

 

300x250
LIST
"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."
0 Comments
댓글쓰기 폼