[프로그래머스] 멀쩡한 사각형 (python)

문제 공유 : http://programmers.co.kr/learn/courses/30/lessons/62048 

코딩테스트 연습 - 멀쩡한 사각형

 

[문제설명]

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

 

[제한사항]

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

[입출력 예]

W	H	result
8	12	80

[입출력 예 설명]

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

 

---

총 5번의 시도로 풀이하였습니다. 

간략하게 최종 코드만 보고 싶다면 맨 밑으로 내리시면 됩니다. 

 

[1차 풀이 설명]

- 입출력 예시와 입출력 그림에서 보았듯이 최대공약수인 4가 관련이 있다고 생각했습니다.

- 최대공약수는 import math 에 gcd() 라는 함수가 있지만, 반복문으로도 처리할 수 있기에 while문으로 해보았습니다.

- 예시처럼 전체 사각형 갯수에서 사용할 수 없는 사각형을 제외시킬려고 하였습니다. 

- 또한 정사각형인 경우 최대공약수와는 관련없이 가로 갯수 만큼만 빼주면 되기에 이런식으로 접근을 해보았습니다.

 

 

[1차 코드]

def solution(w,h):
    answer = w * h

    if w==h:
      return answer = (w*h)-w
    
    # 최대공약수
    while h:
      w,h = h,w%h

    answer -= (w**2)

    return answer

 

[1차 결과]

- 입출력 예시만 통과하고 다른 테스트 예제는 다 틀렸다. (0개)

 

---

[2차 풀이 설명]

- 최대공약수가 아니라 다른 방법으로 풀어야 될 것 같아서 다른 식으로 접근을 해보았습니다.

- 입출력 예시를 보아 80이라는 숫자가 나올려면 w*h에서 긴 쪽인 h에서 -2를 하면 8*10으로 80이 나오는 것 같았습니다.

(그래서 긴 변을 -2를 해주었습니다.)

- 하지만 다른 예시로 w=3, h=5 를 해보았는데 -2를 하면 3*3으로 9가 나오는데, result는 8이 나오므로 -1을 해야되는줄 알았습니다. 

 

[2차 코드]

def solution(w,h):

    if w==h: # 정사각형인 경우
      return answer = (w*h)-w
    elif w > h:
      w -= 2
    else:
      h -= 2
     
     answer = w * h
    if w==h:
      answer -= 1 

    return answer

[2차 결과]

- 입출력 예시는 통과하고 다른 테스트 예제는 2개 맞았습니다.(2개)

 

---

[3차 풀이 설명]

- 2차와 접근법은 똑같고, w=3와 h=5 예시 처럼 곱해서 answer이 홀수이면, -1로 변경해보았습니다.

 

[3차 코드]

def solution(w,h):

    if w==h: # 정사각형인 경우
      return answer = (w*h)-w
    elif w > h:
      answer = (w-2) * h
    else:
      answer = w * (h-2)

     if answer%2 != 0:
       answer -=1       

    return answer

[3차 결과]

- 입출력 예시 통과, 다른 테스트 예제 5개 맞았습니다. (5개)

---

[4차 풀이 설명]

- 예시 그림과 직접 그린 예시를 보다가 사각형이 안된 것을 위로 올려보았습니다.

- 올렸을 시 짧은 변을 기준으로 x2 를 하면 사격형이 안되는 것이 나온다는 것을 알고 짧은 쪽인 변을 찾아 x2를 하여 빼주었습니다.

- 하지만 w=3 h=5 처럼 answer이 홀수이면 사격형이 안되는 것이 1개 더 나오기 때문에 -1을 더 해주었습니다.

 

[추가 설명]

 

[4차 코드]

def solution(w,h):
    answer = w*h
    
    if w==h: # 정사각형인 경우
      return answer = (w*h)-w
    elif w > h:
      answer -= (h*2)
    else:
      answer -= (w*2)

    if answer%2 != 0:
      answer -=1       

    return answer

[4차 결과]

- 입출력 예시 통과, 다른 테스트 예제 5개 맞음(5개)

---

[최종 풀이 설명]

- 위 과정을 통해서 돌고 돌아 다시 최대공약수로 돌아왔습니다. 

(입출력 예 그림이 아무리 봐도 최대공약수로 하라고 할 만큼 너무 명확하게 나와서)

- 2차 시도처럼 어떻게 하면 80이 나올까 생각하다가 이러한 공식이 나오게 되었습니다.

(일단 무조건 전체에서 빼야겠다는 개념으로 시작)

(8 * 12) = 96  // (8 + 12) -4 = 16 // 96 - 16 = 80

 

정리 

answer = (가로 * 세로) - (가로+세로-최대공약수) 

 

[최종 풀이 코드]

def solution(w,h):
    answer = (w*h) - (w+h)
    
    while h: 
        w,h = h,w%h

    answer += w
    return answer

[최종 결과]

- 입출력 예시 통과, 다른 테스트 예제 모두 통과