[2025.01.02] [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합니다.

 

 

제한사항

• 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

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> wallet, vector<int> bill) {
    int answer = 0;
    
    // bill의 작은 값이 wallet의 작은 값보다 클 경우 || bill의 큰 값이 wallet의 큰 값보다 큰 경우
    // (= 지갑에 지폐가 안들어갈 경우)
    while(*max_element(wallet.begin(), wallet.end())<*max_element(bill.begin(), bill.end())
          ||*min_element(wallet.begin(), wallet.end())<*min_element(bill.begin(), bill.end()))
    {
        // 지폐를 접을 때는 항상 긴 쪽을 반으로 접음
        if(bill[0]>bill[1])
        {
            bill[0]/=2; // 반 접기
        }
        else
        {
            bill[1]/=2; // 반 접기
        }
        answer++; // 접은 횟수 업데이트
    }
    return answer;
}

문제가 길어서 겁을 먹을 뻔 했지만 아래로 내리면서 문제를 읽다보니 이미 의사코드까지 작성되어 있었다. 의사코드대로 구현해보도록 하자.

 

결국 쉽게 이야기하면 지폐가 지갑에 들어갈 때까지 접고 접을 때마다 횟수를 업데이트하라는 이야기이다. 몇 번 반복하여 지폐를 접을지 횟수가 명확히 드러나는 상황이 아니므로 while문을 이용하여 작성해주는 것이 좋을 것 같다.

지갑이 지폐에 들어갈 때까지를 나타내는 문장을 어떻게 작성해야 할까? 다행히 의사코드에 이미 적혀있다. 지폐의 작은 부분이 지갑의 작은 부분보다 작아야 하고 동시에 지폐의 큰 부분이 지갑의 큰 부분보다 작아야 한다. 그러면 정확히 이 반대되는 경우 동안에 반복문을 돌리면 된다. 즉, 지폐의 작은 부분이 지갑의 작은 부분보다 크거나 (||) 지페의 큰 부분이 지갑의 큰 부분보다 큰 경우는 지폐를 접는 반복문을 계속 돌리는 것이다.

지폐의 큰 부분과 작은 부분, 지갑의 큰 부분과 작은 부분을 계산하기 위해 max_element와 min_element를 사용하였다. 지폐를 접을 때마다 작은 부분과 큰 부분이 달라질 것이기 때문에 while문 앞에서 큰 부분과 작은 부분을 정의하여 사용하지 않고 while의 조건문 안에서 매번 계산하게 해주었다.

 

다음은 이제 더욱 간단하다. 지폐는 긴 부분을 접는다는 규칙이 있기 때문에 if문을 이용해 긴 부분을 찾고 그 긴부분을 2로 나눠주면 된다. 나머지가 나올 경우 버리라고 하였지만 따로 코드를 작성해줄 필요는 없다. 왜냐하면 우리는 지금 정수 나누기 정수를 하고 있기 때문이다. 실수가 요만큼도 포함되어 있지 않기 때문에 결과값은 자동적으로 정수, 즉 뒤에 소수점이 붙거나 하는 일은 없다는 뜻이다.

 

마지막으로 answer의 값을 +1하여 업데이트 해주면 된다. 지폐가 지갑에 들어가는 순간 반복문을 탈출하게 되고 answer을 리턴하는 것으로 코드가 끝이 난다.

 

 

문제 링크

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

프로그래머스