#10 [PCCE 기출문제] 9번 / 지폐 접기 | 그리디

문제 설명

민수는 다양한 지폐를 수집하는 취미를 가지고 있습니다. 지폐마다 크기가 달라 지갑에 넣으려면 여러 번 접어서 넣어야 합니다. 예를 들어 지갑의 크기가 30 * 15이고 지폐의 크기가 26 * 17이라면 한번 반으로 접어 13 * 17 크기로 만든 뒤 90도 돌려서 지갑에 넣을 수 있습니다. 지폐를 접을 때는 다음과 같은 규칙을 지킵니다.

• 지폐를 접을 때는 항상 길이가 긴 쪽을 반으로 접습니다.
• 접기 전 길이가 홀수였다면 접은 후 소수점 이하는 버립니다.
• 접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있다면 그만 접습니다.

지갑의 가로, 세로 크기를 담은 정수 리스트 wallet과 지폐의 가로, 세로 크기를 담은 정수 리스트 bill가 주어질 때, 지갑에 넣기 위해서 지폐를 최소 몇 번 접어야 하는지 return하도록 solution함수를 완성해 주세요.

지폐를 지갑에 넣기 위해 접어야 하는 최소 횟수를 구하는 과정은 다음과 같습니다.

1. 지폐를 접은 횟수를 저장할 정수 변수 answer를 만들고 0을 저장합니다.
2. 반복문을 이용해 bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
    2-1. bill[0]이 bill[1]보다 크다면
        bill[0]을 2로 나누고 나머지는 버립니다.
    2-2. 그렇지 않다면
        bill[1]을 2로 나누고 나머지는 버립니다.
    2-3. answer을 1 증가시킵니다.
3. answer을 return합니다.

• 위의 의사코드와 작동방식이 다른 코드를 작성해도 상관없습니다.

---

오답

# 지폐접기
# 항상 긴 쪽을 반으로접는다.
# 소수점 이하는 버린다.
# 돌려서 지갑에 넣을 수 있다면 그만 접는다.

 [오답1] 10.0 초과 
 def solution(wallet, bill):
     answer = 0
     # print(f'wallet { wallet }, bill ; {bill}')
     small_wallet = min(wallet[0], wallet[1])
     big_wallet = max(wallet[0], wallet[1])
     small_bill = min(bill[0], bill[1])
     big_bill = max(bill[0], bill[1])
     while small_wallet < small_bill or big_bill > big_wallet:
         if bill[0] > bill[1]:
             bill[0] = bill[0]//2
         else:
             bill[1] = bill[1]//2
   
         answer +=1
       
     return answer

시간초과가 나는이유

- 시간초과의 원인은 small_bill, big_bill 값을 반복문 밖에서 한 번만 계산해 갱신하지 않았기 때문이다.
그래서 실제로 지폐 크기는 줄어드는데 비교 기준은 그대로라 조건이 계속 참이 되어 무한루프에 빠지는 것이다...

 

 

---

시간복잡도 O(log n), 공간복잡도 O(1)

시간복잡도 참고용

- 그리디 알고리즘은 매 순간 가장 최선이라고 판단되는 선택을 반복해 전체 문제의 해를 구하는 방법이다.
각 단계에서의 선택이 전체적으로도 최적이라는 전제 하에 빠르고 효율적으로 문제를 해결한다.

# 지갑은 접지 않으므로, bill만 while문 안으로 넣자.
# 문제는 두개의조건을 만족시켜야 하므로 or이 아니라 and로 
# 종료조건이 복잡할 수록 무한반복 + 종료조건 식으로 하는게좋다. 

def solution(wallet, bill):
    answer = 0
    # print(f'wallet { wallet }, bill ; {bill}')
    small_wallet= min(wallet)
    big_wallet = max(wallet)
    while True:
        small_bill = min(bill)
        big_bill = max(bill)
        if small_wallet >= small_bill and big_bill <= big_wallet:
            break
        
        if bill[0] > bill[1]:
            bill[0] = bill[0]//2
        else:
            bill[1] = bill[1]//2
    
        answer += 1
        
    return answer

---