사용자 도구

사이트 도구


ps:problems:programmers:42842

카펫

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42842
출처프로그래머스
문제 번호42842
문제명카펫
레벨Level 2
분류

수학

시간복잡도O(1)
사용한 언어Python
해결날짜2021/06/08
태그

고득점 Kit - 완전탐색

풀이

  • 세로 길이를 일일히 대입해보면서, 해를 찾을수도 있기는 하다.
  • 하지만, 그냥 식을 세워보면 2차방정식이므로 바로 해를 closed form으로 찾을 수 있다.
  • y = (w-2)(h-2), b = 2*(w+h-2) 로 놓고 w에 대한 2차 방정식으로 정리한 다음, 근의 공식을 적용하면.
    • $ w={\frac {{\frac{b}{2} + 2} + {\sqrt {{\big(\frac{b}{2} + 2}\big)^{2}-4\big(b+y\big)\ }}}{2}} $
    • $ h={\frac {{\frac{b}{2} + 2} - {\sqrt {{\big(\frac{b}{2} + 2}\big)^{2}-4\big(b+y\big)\ }}}{2}} $
  • 그대로 대입해서 풀면 O(1)이다. (sqrt 계산을 O(1)로 가정)

코드

"""Solution code for "Programmers 42842. 카펫".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42842
- Solution link: http://www.teferi.net/ps/problems/programmers/42842
"""

import math


def solution(brown, yellow):
    x = brown // 2 + 2
    y = math.isqrt(x * x - 4 * (brown + yellow))
    return [(x + y) // 2, (x - y) // 2]

토론

댓글을 입력하세요:
W A H᠎ M B
 
ps/problems/programmers/42842.txt · 마지막으로 수정됨: 2021/06/14 13:21 저자 teferi