콜라 문제 (자바, Java)

 

꽤 오래전에 풀었으나, 수수께끼(?)가 최근에 풀려, 이제야 포스팅합니다.

처음에는 반복문인줄 알고, 간단하네~ 하면서 반복문으로 풀었습니다.

 

class Solution {
    public int solution(int a, int b, int n) {
        // a : 빈병의 수 b : 바꿔주는 새로운 콜라의 수 n : 초기 콜라의 수
        int answer = 0;
        while(n>=a) {
            int k = n/a*b;
            n = k + n%a;
            answer+=k;
        }
        return answer;
    }
}

 

문제의 로직을 그대로 반복하여, 더이상 교환이 불가능할때까지 반복하는 방식입니다.

 

충분히 좋은 효율을 보여주긴 하지만, 반복문의 시행횟수가 올라갈수록 연산이 많아지는 구조로 되어있습니다.

 

그리고 충격의 모범답안...

 

class Solution {
    public int solution(int a, int b, int n) {
        return (n > b ? n - b : 0) / (a - b) * b;
    }
}

 

띠용...그냥 수학공식으로 풀었습니다. 문제조건에서 n>=a>b이기 때문에, 삼항연산자도 필요없습니다.

 

여튼, 이 부분이 궁금해서, 수학과 친구에게 물어보았습니다.

그리고, 오늘 그 해법을 듣게되어 포스팅하게 되었습니다.

 

n을 a로 나눈 몫을 m1이라 합시다. 처음에 빈병 am1개로, bm1개만큼의 새로운 빈병을 얻게 됩니다.

bm1을 a로 나눈 몫을 m2라 합시다. 빈병 bm1개로, am2개만큼의 새로운 빈병을 얻게 됩니다.

...

빈병의 갯수가 a개 미만이 될 때까지 반복하게 됩니다.

빈병을 count하면, n(초기 빈병의수) - am1 (반납하는 빈병) + bm1 (새로받은빈병) - am2 + bm2 - (...) 이 됩니다.

이를 묶으면 n-(a-b)(m1+m2+...) 가 됩니다. 여기서 (m1+m2+...) = M으로 놓습니다.

n-(a-b)M은 교환을 못하는 최종적인 빈 병의 갯수이므로, 0보다 커야하고, a보다 작아야합니다.

a>n-(a-b)M 부등식을 M에 대해 정리합니다. M>(n-a)/(a-b).

 

M은 정수입니다. (n-a)/(a-b)의 정수부보다 1큰 수입니다. 그런데, 코딩에서 정수와 정수의 나눗셈은 정수부만 반환합니다.

따라서 M = (n-a)/(a-b)+1 = (n-b)/(a-b) 입니다. 이것이 콜라의 총 교환 횟수입니다.

문제의 정의에서, 한번의 교환으로 얻게되는 빈 병의 갯수는 b입니다. 최종정답은 bM, 즉 b(n-b)/(a-b) 로, 코딩에서 산출한 정답이 나오게 됩니다.

 

 

테스트케이스가 크진 않았는지, 성능차이가 크게 나지는 않았습니다. 테스트12 정도가 좀 두드러지게 차이나는정도?

반복문의 시행횟수가 충분히 작다면, 곱셈/나눗셈보다 덧셈뺄셈의 반복계산이 주는 메리트가 크기 때문일 것입니다.

 

솔직히, 이걸 코딩테스트에서 캐치할 능력은 못 되는 것 같습니다. 그냥 이해하고 넘어가야겠네요.

그럼에도 불구하고, 궁금해서 알아보게 되었습니다.