Menu

Subscribe

[JAVA/프로그래머스] Summer/Winter Coding(2019) : 멀쩡한 사각형

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. 대각선 넓이의 규칙을 찾는다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
	public long solution(int w,int h) {
		long answer = 1;
        if(w<h){ // w가 더 크도록
            int temp=w;
            w=h;
            h=temp;
        }
        int gcd=gcd(w,h);
        answer=(long)w*(long)h-(w+h-gcd);
		return answer;
	}
    
    public int gcd(int a, int b){ // 최대공약수
        if(a%b==0) return b;
        return gcd(b, a%b);
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 대각선 넓이의 규칙을 찾는다
    • 예시에서 똑같은 패턴이 4번 반복됨을 알 수 있다.
    • 4는 8과 12의 최대공약수이다.
    • w=2, h=3일 때 6-4=6-(3+2-1)=w*h-(w+h-1) 식을 도출할 수 있다.
    • 최대공약수가 1 이상이면, gcd만큼 패턴이 반복되는 것이므로 (w/gcd+h/gcd-1)*gcd=w+h-gcd
    • 따라서 해당 문제의 점화식은 w*h-(w+h-gcd)

👏 해결 완료!

참고