[코딩테스트] 2019 Winter Coding 1번 문제

문제

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세 로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기, 입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었 는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러 므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로 운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm x 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

제한사항

W,H: 1억 이하의 자연수

 

입출력 예

W = 8, H = 12, result = 80

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있으므로 96-16=80을 반환합니다.

 

 

 

 

 

---

접근방법

처음에는 모든 경우의 수로 나누어 생각했습니다.

 

1 x 1 = 0

n x n(정사각형) = (w x h) – w

짝 x 홀 / 홀 x 짝 = (w*h) – (둘 중 더 작은 변 x 2 )

 

여기까지는 순조로웠으나..

 

홀 x 홀 = ??

짝 x 짝 = ??

 

여기서부터는 도저히 규칙을 찾을 수가 없었습니다.

...삽질의 향연...

 

도저히 모르겠어서 검색을 하여 대각선이 지나는 격자 점의 개수를 구하는 포스트를 찾게 되었습니다. 

 

대각선이 지나는 사각형의 갯수는 격자점이 존재하는 경우와 존재하지 않는 경우로 나누어 생각해야합니다. 

격자점이 존재하는 경우는 가로와 세로의 최대공약수가 2이상인 경우입니다. 격자점이 존재하지 않는 경우는 가로와 세로, 두 수의 최대공약수가 1인 경우입니다. 

 

즉, 아래처럼 두가지 공식이 나오게 됩니다. 

격자점이 존재하지 않는 경우: (가로) + (세로) - 1

격자점이 존재하는 경우: (가로) + (세로) - 1 - (격자점의 개수) 또는 (가로) + (세로) - (가로 세로 최대공약수)

---

풀이 (Java)

import java.math.BigInteger;

public class Solution{
	
	private static int getGcd(int a, int b){
		BigInteger num1 = BigInteger.valueOf(a);
		BigInteger num2 = BigInteger.valueOf(b);
		BigInteger gcd = num1.gcd(num2);
		return gcd.intValue();
	}
	
	public static int solution(int w, int h){
		int answer;
		int gcd = getGcd(w,h);
		
		if(gcd == 1){
			answer = w + h - 1;
		}else {
			answer = w + h - gcd;
		}
		
		return w*h - answer;
	}
	public static void main(String[] args){
		System.out.println(solution(8,12));
	}
}

 

참고

Java에서 최대공약수를 구하는 방법

 

1. 유클리드 호제법을 통한 직접 구현

2. biginteger클래스의 gcd함수 사용