[프로그래머스] 코딩테스트 연습Summer/Winter Coding(2019)멀쩡한 사각형

문제

문제 설명

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

 

입력 & 출력

입출력 예

WHresult

8

12

80

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

 

풀이 과정

코드2는 시간 초과가 나온 풀이 방법이다. 간단하게 설명하면 짧고 긴 쪽을 판별해서 짧은 쪽을 긴 쪽으로 나눈 값이 짧은 값 크기만큼 자기 자신만큼 증가하는 동안 정수가 아닐 경우에는 2개씩 네모칸에 걸쳐있다고 생각하면서 해당 값을 총값에서 제외시켜주는 방식이었다.

시간을 단축시키기 위해서 첫번째로 짧은 쪽을 긴 쪽으로 나눈 값의 배수가 정수가 되는 경우를 구해서 이 경우 전까지 정수가 아니었던 횟수를 기억하고 이 처음 배수가 되는 숫자로 짧은 값을 나누어졌을 때의 값과 곱하여서 최대 개수에서 빼주는 방식으로 구현하였는데 시간 복잡도가 높아서 시간 초과가 나오게 되었다.

 

코드 1 설명

1. 최대 공약수를 이용하는 방법이다. 

2. 코드2의 방식과 연관성이 있는 내용이지만 잘 생각해보아야 한다. 코드 2번에서는 길고 짧은 위치를 생각함으로써 지나가는 점이 정수가 아닐 경우 *2를 해서 지나가는 타일의 개수를 구하였지만 이번에 하는 코드 1의 방식은 최소 공약수를 구해서 이를 이용 가로 세로 합을 최소 공약수로 나누고 처음에 겹치는 타일이 중복으로 카운트가 되니 -1을 해주는 방식으로 unit 타일 형태에서의 지나가는 타일의 수를 구한다.

3. 2번에서 구한 유닛에서 지나는 타일의 갯수와 최소 공약수를 곱하여서 총 지나는 타일의 개수를 구하게 되며 이를 총정사각형의 개수에서 제외시켜서 answer를 구해내게 된다.

 

 

코드

코드1

def get_gcd(x, y):
    if x < y:
        (x, y) = (y, x)
    while y!=0:
        (x, y) = (y, x%y)
    return x

def solution(w,h):
    answer = w*h
    gcd = get_gcd(w, h)
    unit = (w+h) / gcd - 1
    answer -= unit * gcd
    return answer

 

코드 2

def solution(w, h):
    x_pos = 0
    cnt = 0
    y_pos = 0

    total = w * h
    if w == h:
        answer = total - w
    elif w < h:
        ch = w / h

        x_pos += ch
        while x_pos % 1 != 0:
            cnt += 1
            x_pos += ch

        result = w / x_pos

        answer = int(total - (result*cnt*2))
    else:
        ch = h / w

        y_pos += ch
        while y_pos % 1 != 0:
            cnt += 1
            y_pos += ch

        result = h / y_pos

        answer = int(total - (result * cnt * 2))

    return answer


w, h = input().split()

w = int(w)
h = int(h)

print(solution(w, h))