[PCCE 기출문제] 9번 / 지폐 접기

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

프로그래머스

---

문제 설명
민수는 다양한 지폐를 수집하는 취미를 가지고 있습니다. 지폐마다 크기가 달라 지갑에 넣으려면 여러 번 접어서 넣어야 합니다. 예를 들어 지갑의 크기가 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합니다.

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

---

제한사항

• wallet의 길이 = bill의 길이 = 2
• 10 ≤ wallet[0], wallet[1] ≤ 100
• 10 ≤ bill[0], bill[1] ≤ 2,000

---

입출력 예

wallet	bill	result
[30, 15]	[26, 17]	1
[50, 50]	[100, 241]	4

---

입출력 예 설명
입출력 예 #1

• 지문과 동일합니다.

입출력 예 #2

• 지폐를 접으면 다음과 같이 크기가 줄어듭니다. 따라서 4번 접으면 지갑에 넣을 수 있습니다.
• [100, 241] -> [100, 120] -> [100, 60] -> [50, 60] -> [50, 30]

---

지폐를 지갑에 넣을 수 있을 때까지 접을 때까지 몇 번이 필요한지 구하는 문제입니다.

 

코드를 어떻게 짤지 고민할 필요 없이, 의사코드대로만 따라가더라도 정답 코드를 작성할 수 있습니다.

의사코드에서 명시된 순서로 정답 코드를 작성해보겠습니다.

 

정답 코드

def solution(wallet, bill):
    # 1. 지폐를 접은 횟수를 저장할 정수 변수 answer를 만들고 0을 저장합니다.
    answer = 0
    # wallet의 최대-최소값 / bill의 최대-최소값을 저장합나다.
    minw, maxw = min(wallet), max(wallet)
    minb, maxb = min(bill), max(bill)
    # 2. 반복문을 이용해 bill의 작은 값이 wallet의 작은 값 보다 크거나
    # bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
    while minb > minw or maxb > maxw:
        # 2-1. bill[0]이 bill[1]보다 크다면
        # bill[0]을 2로 나누고 나머지는 버립니다.
        # 2-2. 그렇지 않다면
        # bill[1]을 2로 나누고 나머지는 버립니다.
        maxb //= 2
        if minb > maxb:
            maxb, minb = minb, maxb
        # 2-3. answer을 1 증가시킵니다.
        answer += 1
    # 3. answer을 return합니다.
    return answer

 

저는 굳이 bill[0], bill[1]을 구분해서 문제를 풀지는 않았습니다.

 

의사코드를 살펴보면 bill[0]와 bill[1] 중 큰 값에 대해서 2로 나누고 나머지를 버린다는 코드인데, maxb는 항상 bill 중에서 큰 값을 의미하기 때문에 maxb만 2로 나누고 나머지를 버려주면 됩니다.

 

추가적으로 할 작업은 2로 나눈 maxb가 여전히 큰지, minb보다 작아졌는지만 확인하면 됩니다.

 

minb가 더 커졌다면 maxb, minb의 값을 스왑해주면 됩니다.

 

의사코드대로만 따라갈 수 있다면 간단히 풀 수 있는 문제였습니다.