프로그래머스 - 카펫

lv. 2 단계의 코딩 테스트 연습 문제 중 '카펫'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 카펫

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 원리는 수학적 지식만 있으면 쉽게 풀 수 있었다.
• 먼저 brown은 아래의 수식을 따른다(x: 가로, y: 세로).
  
  • x + y = (brown + 4) / 2
• 그리고 yellow는 아래의 수식을 따른다.
  • (x-2) * (y-2) = yellow
• brown 수식에서 x > y보다 항상 크다는 조건이 있기 때문에, 우항을 t라 할 때 t가 되도록 하는 x + y를 모두 탐색하면 된다.
  • 예를 들어서, brown이 10이면
  • x + y = 14 / 2 = 7이기 때문에
  • x = {7, 6, 5, 4} 가 된다.
  • 이 때, yellow가 2라면 yellow 수식까지 만족하는 것은 x가 4일 때 이므로 정답은 x는 4, y는 3이 된다. 
• 수식의 for문(x의 범위)에서 ceil이 쓰이는 이유는 t가 실수가 될 때를 고려해서 이다.
  • 예를 들어, t가 9이면 x는 { 9, 8, 7, 6, 5 } 의 범위를 가져야 한다.
  • 9 / 2 = 4.5이기 때문에 버림을 할지 올림을 해야 할지 결정해야 한다.
  • 그렇다면 t가 짝수면 어떻게 될까?
  • t가 10이라면, 10 / 2 = 5이기 때문에 x는 {10, 9, 8, 7, 6, 5 }의 범위를 지녀야 한다.
  • 아하, 그러면 for의 범위는 ( t, (t / 2) - 1 ) 구나! 라고 정할 수 있다(for문의 2번째 인자는 범위에 포함되지 않으므로, -1을 해준다).
    
    • 그러면 4.5가 나올 때, 버림을 해서 4로 만들면 4 - 1 = 3 이므로, (9, 3) 까지의 범위를 가져버리게 된다.
    • 이러면 안되니까 올림을 해보자
    • 올림을 해서 5로 만들면 5 - 1 = 4 이므로 (9, 4) 까지의 범위를 가지므로 적절하다.
• 코드는 아래와 같다.

코드

import math
def solution(brown, yellow):
    answer = []
    
    limitX = (brown + 4) // 2
    
    for x in range(limitX, math.ceil(limitX / 2) - 1, -1):
        y = limitX - x
        if (x-2)*(y-2) == yellow:
            answer.append(x)
            answer.append(y)
            break
    return answer

 

설명은 거창했으나, 실질적으로 코드는 간단하다.

 

추천글

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스