프로그래머스

프로그래머스 지폐 접기 풀이: 긴 변을 줄이는 그리디

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

지갑의 크기 wallet과 지폐의 크기 bill이 주어집니다. 지폐를 지갑에 넣을 수 있을 때까지 다음 규칙으로 접습니다.

  • 항상 현재 길이가 긴 쪽을 반으로 접습니다.
  • 홀수 길이를 접으면 소수점 이하는 버립니다.
  • 지폐는 그대로 넣거나 90도 회전해서 넣을 수 있습니다.

지폐를 지갑에 넣기 위해 접어야 하는 최소 횟수를 구합니다.

지폐가 지갑에 들어가는지 확인할 때는 방향을 바꿀 수 있으므로 다음처럼 작은 변과 큰 변을 비교하면 됩니다.

min(bill) <= min(wallet)
max(bill) <= max(wallet)

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택

현재 지폐가 지갑에 들어가지 않는다면, 문제에서 정한 규칙에 따라 긴 변을 접어야 합니다. 다른 변을 선택할 수 있는 상황이 아니므로 매 단계에서 가능한 선택은 하나입니다.

따라서 다음 과정을 반복합니다.

  1. 지폐의 작은 변과 큰 변을 지갑의 작은 변과 큰 변에 맞춰 비교합니다.
  2. 지갑에 들어가지 않으면 지폐의 긴 변을 // 2로 줄입니다.
  3. 접은 횟수를 1 증가시킵니다.
  4. 지폐가 들어갈 때까지 반복합니다.

회전 가능한 직사각형 비교

예를 들어 지갑이 [30, 15], 지폐가 [26, 17]이면 지갑을 [15, 30]으로 생각할 수 있습니다. 지폐를 한 번 접어 [13, 17]로 만들면 작은 변 13은 15 이하이고 큰 변 17은 30 이하이므로 회전해서 넣을 수 있습니다.

지갑과 지폐의 순서를 매번 직접 바꾸기보다 min과 max를 사용하면 두 방향을 한 번에 검사할 수 있습니다.

복잡도

지폐의 긴 변은 접을 때마다 절반으로 줄어듭니다. 지폐의 최대 변을 B라고 하면 접는 횟수는 O(log B)이고, 문제의 제한에서는 매우 작습니다. 추가로 사용하는 공간은 변수 몇 개뿐이므로 O(1)입니다.

핵심 관찰

회전 가능 여부는 작은 변끼리, 큰 변끼리 비교하는 문제입니다. 접는 방향도 임의 선택이 아니라 항상 현재 긴 변으로 고정되어 있으므로, min·max 비교와 반복문으로 규칙을 그대로 옮길 수 있습니다.

오답 접근과 반례

첫 번째 변을 무조건 접으면 틀릴 수 있습니다. bill = [10, 26]에서는 26을 접어야 하는데 첫 번째 변을 줄이면 10을 줄이게 됩니다. 매 반복마다 현재 두 변의 크기를 다시 비교해야 합니다.

3. 문제 해결 코드 (Python)

def solution(wallet, bill):
    count = 0

    while min(bill) > min(wallet) or max(bill) > max(wallet):
        if bill[0] > bill[1]:
            bill[0] //= 2
        else:
            bill[1] //= 2
        count += 1

    return count

구현 포인트

  • min과 max를 이용해 지폐를 90도 돌리는 경우까지 함께 확인합니다.
  • bill[0] > bill[1]이면 첫 번째 변, 그렇지 않으면 두 번째 변을 접습니다.
  • 접기 전 길이가 홀수여도 // 2가 소수점 이하를 자동으로 버립니다.
  • 지폐가 지갑에 들어간 순간 반복을 종료하므로 최소 횟수가 됩니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 문제에서 제시한 과정을 그대로 반복하는 구현 방식과, 두 직사각형의 작은 변·큰 변을 비교하는 그리디 방식으로 나뉩니다.

다른 풀이에서도 핵심은 동일합니다. 이 문제는 접을 방향을 임의로 선택하는 문제가 아니라 항상 긴 변을 접어야 하므로, 매 단계의 선택이 고정되어 있습니다. 이 글에서는 회전 가능 여부를 min·max 비교로 표현해 별도의 정렬이나 배치 배열 없이 처리했습니다.

마무리

직사각형을 회전해서 넣을 수 있는 문제는 작은 변과 큰 변을 나누어 비교하면 조건을 간단히 만들 수 있습니다. 이 문제처럼 매번 정해진 규칙에 따라 긴 변을 줄이는 경우에는 현재 상태가 목표 조건을 만족할 때까지 한 가지 선택을 반복하는 그리디 풀이가 가장 자연스럽습니다.

#그리디#프로그래머스#난이도 1