강의실/정보영재

2016년 서울대학교 프로그래밍 경시대회 A번에 다음과 같은 문제가 나왔네요.

 

이미지 출처 - https://www.acmicpc.net/problem/13199

 

이 문제를 이해하는데 조금 시간이 걸렸는데요.

예제 입력에서 통닭 한마리 값이 10000원이고 두영이와 상언이가 50000원을 가지고 있는데 상언이가 몇마리를 더 먹을 수 있을까 묻는 문제인데요.

일단 이 문제에서는 두영이와 상언이는 치킨을 시킬때 마다 쿠폰을 받고

단골 손님인 상언이는 쿠폰을 가지고 시켰을 경우에도 쿠폰을 받는다 였는데

실수로 돈내고 시킬때도 상언이만 쿠폰을 받는 것으로 착각을 했던 문제네요.^^

이만큼 문제를 읽는데 실수를 하면 많은 시간을 헤메이게 되는데요.

(알고리즘 문제는 실생활속의 상황을 녹이기는 하지만 실생활과는 약간 다르기 때문에 문제를 정확히 이해하는게 새삼 중요하다는것을 느꼈네요.)

 

따라서 5만원으로 통닭 5마리를 시키고 쿠폰 5장을 받아서 통닭을 시켜 먹었을때 두영이는 쿠폰 한장을 가지고 있고 상언이는 쿠폰이 0장 

따라서 두영이 6마리 상언이 6마리 이기 때문에 차이가 0 이라서 출력이 0 이 되는 케이스 입니다.

그렇다면 이런 문제는 어떤 식으로 접근을 해야 할까요?

가장 단순한 접근 방법으로는 두영이와 상언이가 먹을 수 있는 양을 먼저 체크 합니다.

50000원을 가지고 있으면 10000 원짜리  5마리 (50000 / 10000 )

이렇게 계산을 하면 먹은 양을 가지고 두영이와 상언이가 받은 쿠폰을 구할 수가 있겠네요.

가령 1마리에 쿠폰 3장씩을 준다고 하면 5마리 * 3 = 15장

이때까지는 두영이와 상언이가 먹은 갯수가 동일 합니다.

여기에서 두영이는 단골이 아니기 때문에 쿠폰으로 먹을때는 쿠폰을 받지 못합니다.

만약 쿠폰 5장으로 한마리로 바꾼다고 하면 두영이는 쿠폰 15장 / 5장 으로 3마리를 더 시켜 먹을 수 있겠네요.

상언이는 쿠폰 15장으로 3번을 시켜 먹으면 3 * 3 = 9장의 쿠폰을 다시 얻게 됩니다.

이때 5장의 쿠폰을 가지고 한마리를 더 시켜 먹으면 4장 + 3장 = 7장이 되므로 또 한마리를 시켜 먹을 수 있습니다.

그 다음 5장을 가지고 더 시켜 먹으면 2장 + 3장 = 5장이므로 또 한마리를 시켜 먹을수 있습니다.  

 

이것을 하나씩 빼면서 계산하면 시간초과를 만날 수도 있겠는데요.

나눗셈을 이용해서 계산하면 빠른 시간에 해결 할 수 있습니다.

이때 계산 방법은 두영이는 단순하게 먹은 마리수를 (가지고 있는 쿠폰수)/(공짜로 시킬 쿠폰수) 를 더해 주면 됩니다.

상언이는 조금 생각해 보아야 하는데요 15장의 쿠폰을 가지고 있다면 5장 사용후 3장을 다시 얻게 됩니다.

즉 가지고 있는 쿠폰수에서 (공짜로 시킬 쿠폰수 - 받는 쿠폰수) 만큼씩만 빠지게 되면 그때마다 한마리씩을 먹게 되는 것입니다.

따라서 (가지고 있는 쿠폰수) / (공짜로 시킬 쿠폰수 - 받는 쿠폰수) 를 하면 상언이가 먹는 수가 나오는데요.

여기서 문제가 있습니다.

공짜로 시킬 쿠폰수가 5장이고 받는 쿠폰수가 3장일때 한번 시킬때마다 2장씩이 주는데...

위의 계산식으로 할때 쿠폰 4장이면 2마리를 먹게 되는 형태가 발생합니다.

따라서 처음 가지고 있는 쿠폰수 15장에서 처음 공짜로 시켜 먹는 쿠폰수 5장을 빼고 남은 수에서  (공짜로 시킬 쿠폰수 - 받는 쿠폰수) 로 나누어서 계산을 해 주면 됩니다.

 

#include <stdio.h>


int main()
{
    int doyung, sangun, docnt, sangcnt;
    int P, M, F, C;
    int cnt;

    scanf("%d", &cnt);

    while (cnt--) {
        scanf("%d %d %d %d", &P, &M, &F, &C);

        doyung = docnt = sangun = M / P;
        docnt = sangcnt = docnt * C;
        doyung += docnt / F;
        //상언이는 f장을 가지고 시켜 먹은 후에는
        //공짜로 시켜먹는 쿠폰 - 딸려오는 쿠폰 수만큼에 한마리씩을 먹게 된다.
        if((sangcnt - F) > 0)  sangun += (sangcnt - F) / (F-C) + 1;


        printf("%d\n", sangun - doyung);
    }

    return 0;
}

 

 

c언어로 구현을 해 보면 위와 같습니다.

서울대생이 푸는 치킨 문제를 풀어 보았는데요.^^

이 문제를 풀다 보니 두마리 치킨이 땡기네요.^^

 

 

 

4 0
  • 핑구야 날자 2019.04.18 06:44 신고    

    관련 문제를 자주 푸는 게 중요한 거 같아요

  • 휴식같은 친구 2019.04.18 08:37 신고    

    머리좀 써아겠어요.
    잘 보고 갑니다.

  • 공수래공수거 2019.04.18 09:13 신고    

    알듯하면서도 어렵네요. ㅎ

  • 버블프라이스 2019.04.18 19:08 신고    

    2016년 서울대학교 프로그래밍 경시대회 A번 문제 풀이를 해주셧군요? 많은 문제들을
    풀어보고 경험을 쌓는것이 중요한 것 같습니다^^