[백준] 4796번: 캠핑 (C++)

그리디 알고리즘으로 푸는 문제

그리디 알고리즘으로 발제를 진행한 후,

원리나 작동 방식은 이해했지만 정작 코딩 경험이 부족했다

이해한 부분을 코드로 풀어쓰는 게 쉽지 않아 

쉬운 문제부터 차근차근 풀어보기로 했다

 

0을 입력 받기 전까지 수 3개를 입력 받는다

최대 기간(p) 중 연속으로 사용 가능한 날짜(l)을 입력 받고 전체 휴가 기간(v)을 입력 받는다

 

우선 전체 휴가 기간 중 최대 기간만큼 나눈 몫만큼은 사용 가능한 것이 보장되어 있으니

나눈 몫에 연속으로 사용가능한 날짜를 곱해 사용 가능한 날짜를 저장한다

 

그 다음 몫으로 나눈 나머지에 대해

연속으로 사용 가능한 날짜보다 큰 경우 최대로 연속으로 사용 가능한 날짜를 더하고

연속으로 사용 가능한 날짜보다 작은 경우 남은 날짜만큼 더하서 완성한다

 

 

// baekjoon 4796

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int main(){
    init();
    
    int l = 1, p = 1, v = 1;
    
    
    int i = 0;
    int day = 0;
    
    while (1) {
        cin >> l >> p >> v;
        if(l == 0 && p == 0 && v == 0)
            break;
        day = 0;
        day += (v / p) * l;
        
        if(v % p > l){
            day += l;
        }
        else{
            day += v % p;
        }
        
        i++;
        cout << "Case " << i << ": " << day <<  '\n';
    }
    
}

 

6달 전에도 똑같이 while 문을 사용하여 풀었지만

실행 시간이 단축되었다

어떠한 차이로 시간이 단축되었는지 궁금하다