[문제 풀이] 백준 4796번 캠핑 JAVA

문제

 

  문제접근 방법   

해당 문제는 캠핑을 갔는데 캠핑장에 연속하는 P일 중 L일만 사용가능하다는 경고문이 존재했다.

이때 휴가를 V일이라 하면 휴가기간에 최대로 캠핑장을 이용할 수 있는 일 수를 구하는 프로그램을 작성하는 문제이다.

문제를 읽어보니 총 휴가일을 P일로 나누고 문제를 접근하면 되겠다고 생각했고 아래와 같이 코드를 작성하였다.

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int i=1;
        while(true){
            int l=s.nextInt();
            int p=s.nextInt();
            int v=s.nextInt();
            if(l==0&&p==0&&v==0)break;
            System.out.println("Case "+i+": "+(v/p*l+v%p));
            i++;
        }
        
    }
}

총 휴가일 v를 p로 나누면 몫과 나머지 값이 나오는데 이때 어차피 p가 반복되는 만큼 l도 반복될 수 있는 것이기 때문에 v/p를 l과 곱해주고 나머지 값을 더해주면 휴가기간 동안 캠핑장에 머무를 수 있는 최대 일 수를 구할 수 있게 되는 것이다.

예를 들어 총휴가일이 20일이고 캠핑장에는 연속하는 8일 중 5일까지만 머무를 수 있다고 생각해 보면 8일로 20일 나누면 2번 반복하고 나머지가 4 남는 것을 확이해 볼 수 있다. 어차피 8일 중 5일만 가능하기 때문에 8일이 2번 반복 == 캠핑장에 머무를 수 있는 시간은 5 * 2와 같다. 그리고 남은 일수를 더해주면 최대 일수를 구할 수 있는 것이다.  

하지만 틀렸다는 결과를 받아 문제를 재분석해 아래와 같이 수정하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int i=1;
        while(true){
            int l=s.nextInt();
            int p=s.nextInt();
            int v=s.nextInt();
            if(l==0&&p==0&&v==0)break;
            int temp=v%p>l?l:v%p;
            System.out.println("Case "+i+": "+(v/p*l+temp));
            i++;
        }
        
    }
}

초기 코드에서는 나머지 값을 무조건 더해주었는데 이렇게 되면 연속하는 p일중 l일만 사용가능하다는 규칙을 지키지 못하게 되는 경우가 발생한다. 예를 들어 8일중 5일 사용가능하고 휴가를 23일 사용할 수 있다면 23/8 = 2 , 23% 8= 7이다.

여기서 초기 코드처럼 나머지를 무조건 더 해주면 규칙이 어긋나 버리는 것이다. 그래서 이를 해결하기 위해서 l값과 나머지 값을 

비교해서 더 작은 값을 저장하는 방식으로 수정해 코드를 완성하였다.

 

  추가 코드 분석   

해당 문제를 본인은 수학적으로만 생각하고 접근하였지만 해당문제의 알고리즘 분류는 수학, 그리디 알고리즘 이라고 명시되어 있다. 이를 인지하지 못하고 문제를 풀었기 때문에 잠깐 설명하도록 하겠다. 물론 수학적으로 접근하던지 그리디 알고리즘으로 접근하던지 결국 답은 같다. 하지만 2가지 모두 인지하고 있냐 없냐는 차이가 있다고 판단해 아래 정리해 보도록 하겠다.

 

그리디 알고리즘이란? 

순간순간마다 최적의 선택을 하고, 그 선택들이 모여 전역적으로 최적의 해가 되는 알고리즘을 의미한다. 

최적의 순간이란 현재 시점에서 가장 좋아 보이는 선택을 의미한다. 

그렇다면 아래의 조건에 만족하면 그리디 알고리즘을 활용해 문제해결이 가능하다는 것을 의미한다.

 

- 순간순간 최선의 선택이 전체 최적해를 보장하는가?

• P일자리 구간을 기준으로 생각
• 매 구간에서 사용할 수 있는 날은 최대 L일 
• 따라서 매구 간에서 최대한(L일) 사용한다는 선택이 최선의 선택
• 즉 한 구간에서 L일보다 덜 쓰는 것은 손해
• 매 순간 L일을 꽉 채워 쓰는 것이 최선이다.
• 매 구간 최대로 사용하는 것보다 좋은 방법은 존해자지 않는다.
• 마지막 잔여 구간도 가능한 만큼 다 쓰기가 최적
• 즉, 그리디 선택이 전역적으로든 국소적으로든 최적 의해라는 것이 증명

    -> 그런 이유로 그리디 알고리즘의 시각으로도 문제를 해석할 수 있다.

 

  마무리  

문제를 보고 수학적으로만 판단했었는데 무의식적으로 그리디 알고리즘을 사고하고 있었다. 하지만 인지를 못하고 있었을 뿐이었다는 것을 깨달았고 이번 기회를 통해 그리디적 사고에 익숙해지고 순간순간 바로 떠올릴 수 있도록 연습해야겠다.