프로그래머스 [PCCE 기출문제] 9번 / 지폐 접기(C++) -yes6686- 티스토리

프로그래머스 문제 풀이: [PCCE 기출문제] 9번 - 지폐 접기

---

문제 설명:

주어진 지폐의 크기와 박스 크기가 있을 때, 지폐를 접어서 박스 안에 넣을 수 있도록 하는 최소 접기 횟수를 구하는 문제입니다. 지폐는 가로 또는 세로 중 하나가 박스 크기보다 크면 접어야 하며, 접을 때 해당 변의 길이는 절반이 됩니다.

---

문제 해결 코드

#include <vector>
using namespace std;

int solution(vector <int> w, vector <int> b) {
    int ans = 0;  // 접기 횟수 초기화
    
    while (true) {
        // 지폐가 현재 방향으로 박스에 들어갈 수 있는지 확인
        if ((w[0] >= b[0] && w[1] >= b[1]) || (w[0] >= b[1] && w[1] >= b[0])) {
            break;  // 조건 충족 시 종료
        }
        
        // 들어가지 않을 경우, 더 긴 쪽을 접는다
        if (b[1] > b[0]) {
            b[1] /= 2;  // 세로 길이 접기
        } else {
            b[0] /= 2;  // 가로 길이 접기
        }
        
        ans++;  // 접기 횟수 증가
    }
    
    return ans;
}

---

코드 설명

• 핵심 알고리즘: 반복문을 사용하여 지폐의 한 변이 박스보다 클 경우 해당 변을 절반으로 줄이는 과정을 진행합니다. 이 과정은 최종적으로 지폐가 박스 안에 들어갈 때까지 반복됩니다.
• 구현 세부사항:
• 두 가지 방향(가로와 세로)을 모두 고려하며, `w[0]`과 `w[1]`을 비교해 최소 접기 횟수를 계산합니다.
• 매 반복마다 현재 지폐 크기(`b`) 중 더 긴 쪽을 선택하여 절반으로 줄이고 접기 횟수를 증가시킵니다.
• 시간 복잡도 분석:
• 각 반복에서 한 변을 절반으로 줄이므로, 한 변이 1이 될 때까지의 반복 횟수는 log2(max(b[0], b[1]))에 비례합니다.
• 따라서, 총 시간 복잡도는 O(log(max(b[0], b[1])))입니다.

---

결과

이 코드는 지폐를 접어 박스 안에 넣는 최소 접기 횟수를 정확히 계산합니다. 간단한 논리로 구현되었으며, 제한된 크기의 문제에 대해 효율적으로 작동합니다.

대체 접근 방식으로, 박스와 지폐의 비율을 미리 계산하여 조건부로 접기 횟수를 구하는 방법도 고려할 수 있습니다. 이러한 방법은 반복 횟수를 줄일 수 있으나 구현의 복잡성이 증가할 수 있습니다.