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

 

 

 

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

 

 

문제 3줄 요약

 

1. 지갑 크기의 맞게 지폐를 넣고자 한다.

2. 지폐가 지갑의 크기보다 크다면, 지폐의 긴 쪽을 반으로 접는다.

3. 최소 몇 회를 접어야 넣을 수 있나?

 

---

 

문제 내에 의사코드도 주어져 있어서

풀기에 큰 어려움이 없지 않았나 싶었던 문제였다.

 

문제를 파악 후

가장 먼저 작성하고자 했던 것은

지폐와 지갑의 크기를 정렬하고

큰 부분끼리 비교해보자...! 였다.

 

지폐와 지갑의 크기가 벡터로 주어졌기에

 

    #include <algorithm>
    
    sort(wallet.begin(), wallet.end());
    sort(bill.begin(), bill.end());

 

다음과 같은 "algorithm" 선언과

sort를 이용하여 오름차순 정렬해주었다.

 

두 벡터 모두 크기가 2로 고정되어 있기에

자연스레 긴 부분은 [1] 에 저장되어 있고

짧은 부분은 [0] 에 저장되어 있겠다.

 

    while(wallet[0]<bill[0] || wallet[1]<bill[1])
    {
        if(wallet[1]<bill[1] || wallet[0]<bill[0])
        {
            bill[1] /= 2;
            answer++;
        }

        if(bill[1]<bill[0])
            sort(bill.begin(), bill.end());

    }

 

따라서

반복문을 돌며 지갑보다 지폐 길이가 클 경우에는

반으로 접어준다.

 

그냥 접어주는 것이 아니라

'긴 쪽'을 반으로 접어야 하기 때문에

우린 [1] 의 값을 반으로 나눠줄 것이고

접은 횟수를 1 증가한다.

 

접은 이후

짧았던 부분이 이제 반으로 접힌 긴 쪽보다 길다면,

다시 정렬해주어서 [1] 에 긴 것이 위치하도록 하였다.

 

 

처음에 긴 쪽으로만 접어야 하는 것을

잊고 문제를 풀고 제출하여

테스트 케이스가 한 3개 정도..? 통과 되지 않았다.

 

 

위의 코드를 조합해보면!

 

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

using namespace std;

int solution(vector<int> wallet, vector<int> bill) {
    int answer = 0;
    
    sort(wallet.begin(), wallet.end());
    sort(bill.begin(), bill.end());
    
    while(wallet[0]<bill[0] || wallet[1]<bill[1])
    {
        if(wallet[1]<bill[1] || wallet[0]<bill[0])
        {
            bill[1] /= 2;
            answer++;
        }

        if(bill[1]<bill[0])
            sort(bill.begin(), bill.end());

    }
    return answer;
}

 

 

---

 

반복문과 분기문을 연습하기 좋은 문제..

라고 느꼈다 ㅎ

 

끝!