[프로그래머스]카펫

[67] 카펫

책 구매하기

문제 정보

• 분류: 시뮬레이션
• 정답률: 70%
• 권장 시간 복잡도: O(sqrt(B))
• 핵심 키워드: 약수, 가로/세로, 면적, 완전 탐색
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42842

문제를 읽을 때 체크할 포인트

노란색 격자의 가로세로를 약수로 나눠 보면서, 바깥 테두리 갈색 칸 수가 맞는지를 확인하면 된다. 식을 세워도 되고 약수 탐색으로 가도 된다.

규칙을 그대로 따라가는 문제처럼 보여도 상태를 어떻게 단순하게 들고 갈지가 더 중요하다. 좌표나 값의 변화만 깔끔하게 관리하면 의외로 짧게 끝난다.

풀이 흐름

1. yellow의 약수 쌍을 찾는다.
2. 각 약수 쌍을 내부 가로/세로라고 보고 바깥 크기를 2씩 더한다.
3. 그때 갈색 칸 수가 brown과 같으면 정답이다.

구현할 때 놓치기 쉬운 부분

노란색 격자 수와 갈색 테두리 수를 동시에 만족하는 가로, 세로를 찾아야 한다. 약수를 찾더라도 테두리 계산이 맞는지 다시 확인해야 한다.

파이썬 정답 코드

def solution(brown, yellow):
  # yellow의 약수 쌍을 찾는다.
  for h in range(1, int(yellow ** 0.5) + 1):
    # 각 약수 쌍을 내부 가로/세로라고 보고 바깥 크기를 2씩 더한다.
    if yellow % h != 0:
      continue
    w = yellow // h
    if (w + 2) * (h + 2) == brown + yellow:
      return [w + 2, h + 2]

시간 복잡도

B는 yellow 영역의 넓이다.

약수는 짝으로 생기므로 한쪽만 확인하면 된다. 그래서 1부터 B 전체를 다 보지 않고 제곱근 sqrt(B)까지만 검사하면 충분한다.

따라서 시간 복잡도는 O(sqrt(B))이다.