[Programmers] 위클리 챌린지 | 1주차_부족한 금액 계산하기

문제 설명

 

새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이용료가 100이었다면 2번째에는 200, 3번째에는 300으로 요금이 인상됩니다.
놀이기구를 count번 타게 되면 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 return 하도록 solution 함수를 완성하세요.
단, 금액이 부족하지 않으면 0을 return 하세요.

 

제한사항

• 놀이기구의 이용료 price : 1 ≤ price ≤ 2,500, price는 자연수
• 처음 가지고 있던 금액 money : 1 ≤ money ≤ 1,000,000,000, money는 자연수
• 놀이기구의 이용 횟수 count : 1 ≤ count ≤ 2,500, count는 자연수

---

입출력 예

 

price	money	count	result
3	20	4	10

입출력 예 설명

 

입출력 예 #1
이용금액이 3인 놀이기구를 4번 타고 싶은 고객이 현재 가진 금액이 20이라면, 총 필요한 놀이기구의 이용 금액은 30 (= 3+6+9+12) 이 되어 10만큼 부족하므로 10을 return 합니다.

 

풀이1

class Solution {
    public long solution(int price, int money, int count) {

        int sum = 0;
        for(int i = 1; i<=count; i++){
            sum += (price*i);
        }    
        
        return (sum > money) ? (sum-money) : 0;

    }
}

채점 결과

정확성: 78.3

합계: 78.3 / 100.0

 

풀이2

class Solution {
    public long solution(int price, int money, int count) {

        long sum = 0;
        for(int i = 1; i<=count; i++){
            sum += (price*i);
        }    
        
        return (sum > money) ? (sum-money) : 0;

    }
}

 

 

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

int sum을 long sum으로 변경하니 해결되었다.

제한사항을 살펴보면 price와 count의 최대값은 2500이다. 최대값으로 테스트를 수행하면 int의 최대범위를 넘어서기 때문에 overflow가 발생한다. 따라서 long으로 반환해야 한다.

 

다른 사람의 풀이

class Solution {
    public long solution(int price, int money, int count) {
        long answer = -1;
        answer = (long)price*count*(count+1)/2 - money;
        return answer<=0 ? 0 : answer;
    }
}

놀이기구 타는 횟수 count에 따른 총 이용 금액을 구하는데 자연수 거듭제곱의 합 개념인 등차수열의 합 공식을 활용했다. 

 

등차수열의 합을 구하는 방법, 즉 어떤 숫자부터 어떤 숫자까지의 합을 구하는 방법은 다음과 같다.

price	money	count	result
3	20	4	10

이 예시를 가지고 등차수열의 합을 구해보자. 이용금액 3인 놀이기구를 4번 타면, 3,6,9,12 순서로 금액이 증가한다. 

3,6,9,12 순서대로 나열한 a와 12,9,6,3 거꾸로 나열한 a 두 개의 항이 있다.

 

a = 3-6-9-12

a = 12-9-6-3

이 되는데, 살펴보면 a, a 같은 순서에 있는 항끼리 더하면 모두 15로 같다. 15인 항이 4개 있으니까 그 합은 15 X 4가 된다. 그런데 a, a 이렇게 두 개의 값을 합친 것이니 2a라고 할 수 있다. 그래서 나누기 2를 해준다. 그러면 값은 30이 된다.

 

이를 정리하면 다음과 같다.

2a = (3+12) + (6+9) + (12+3) + (9+6)

2a = 15 + 15 + 15 + 15

2a = 15 X 4

a = 30

즉 3,6,9,12를 모두 더하면 30이 나온다.

 

이 개념을 활용해 1부터 count까지의 합을 구한 뒤(count*(count+1)/2) price를 곱하면 놀이기구 타는 횟수 count에 따른 총 이용 금액을 구할 수 있다.