[백준] 4796번 문제 풀이

www.acmicpc.net/problem/4796

4796번: 캠핑

 

내가 문제를 해결하기 위해서 가장 먼저 생각하는 것은 예제에서 주어지는 입력으로 어떻게 출력 값이 나왔지? 에 대한 의문점이다.

 

풀이 :

입력으로 각각 L = 5, P = 8, V = 20이 주어졌다면, 어떻게 해서 출력값이 14가 나왔을까?
문제에서 나온 지문을 그대로 가져와서 보자.

"캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일자리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠 동안 사용할 수 있을까? (1 < L < P < V)"

강산이가 20(V)일의 휴가를 받고 캠핑장을 여는 8(P) 일간 5(L) 일만 사용이 가능한 것이다.

20일의 휴가를 받았을 때 캠핑장을 이용할 수 있는 일수

위 그림처럼 파란색으로 색칠되어 있는 날짜가 캠핑을 사용할 수 있는 날짜이다. 그렇다면 빨간색으로 색칠되어 있는 날은 뭘까? 주어진 8(P) 일 중에 캠핑장을 사용할 수 없는 날이다. 왜냐하면 캠핑장을 8(P) 일 중에 5(L) 일동 안 만 사용 가능하기 때문이다. 계속 똑같은 얘기를 반복하는 중이다.

 

이제 어떤식으로 구할 수 있는지 어렴풋이 알 것 같다.

만약 다음과 같은 입력이 주어진다면?

입력 : 5 8 17

출력 : 11

17일의 휴가를 받았을 때 캠핑장을 이용할 수 있는 날

주어진 입력값들을 위의 그림에 대입해보면 아까와 똑같이 직관적으로 답을 알 수 있다.

그렇다면 아무렇게나 주어지는 입력값(테스트 케이스)들을 모두 통과하려면 어떻게 공식을 써야 할까?

 

잠시 생각을 해보자...

 

만약에 5 8 8이 주어졌다고 가정을 해보면 당연하게 출력 값은 5가 나오게 된다. 그 이유는 휴가가 8일이 주어졌는데 그중에서 8일간 캠핑장을 여는데 5일 동안만 사용이 가능하니까(뭐 주인장 허락 안 받고 무단 침ㅇ..)

그런데 5 8 9가 주어진다면 출력 값은 6이 나온다!!!

왜냐하면 이전에 있었던 8일은 이미 지나버렸고 또다시 새로운 8일이 시작되었기 때문에 또 캠핑장을 사용할 수 있는 것이다. (예를 들어 게임에서 랭킹전이나 이벤트가 매주마다 시작되는 경우)

 

이제 결론이당... 핵심적인 코드부터 먼저 보시죠!

res = min(v % p, l) + (v / p) * l;

 

위의 공식을 해석해보면

최소한 사용할 수 있는 캠핑장 이용일 : (v / p) * l

min(v % p, l) 이건... 아무리 생각해봐도 한 번에 정의할 수 있는 문장이 없다...(죄송합니다)

사실 내가 이 문제를 풀면서 계속 막혔었던 부분도 "min(v % p, l)"이다.

분명히 저 공식에 다른 값들을 넣어보면 정확히 예상한 대로 동작하지만, 어떻게 해서 저 공식을 생각해냈는지 궁금하다.

"(v / p) * l + (v % p)"이 식은 내가 스스로 생각을 했지만 더 생각이 앞으로 나아가지 못했었다...

 

최종 코드

#include <iostream>
using namespace std;

int main()
{
  int i = 0, l, p, v, res = 0;
  while (true)
  {
    cin >> l >> p >> v;
    if (l == 0 && p == 0 && v == 0)
      break;
    res = min(v % p, l) + (v / p) * l;
    cout << "Case " << ++i << ": " << res << "\n";
  }
  return 0;
}

 

어쨌든 이렇게 강산이가 며칠 동안 캠핑장을 사용할 수 있는지에 대한 문제를 풀어봤다.

 

참조

eocoding.tistory.com/53

[백준] 4796번_캠핑 C++ 풀이