Lv1_[부족한 금액 계산하기, C++] 알고리즘 정리 - 프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

 

간단한 풀이 방식은 반복문에 넣어서 모든 값을 더해주면 되지만, 위의 문제는 패턴이 있는 덧셈이기 때문에 수식화 하면 간단히 풀 수 있다.

 

★ 수식화

동일한 간격의 수를 더하는 공식을 계산해보자.
· 3 + 6 + 9 + 12  (price : 3, count : 4)

맨 앞과 뒤를 더하고 총개수의 절반만큼 곱해주면 된다.
· (3 + 12) + (3 + 9) = (3 + 12) * (4 / 2) = 30

count를 하나 더 늘리면

3 + 6 + 9 + 12 + 15  (price : 3, count : 5)
· (3 + 15) + (3 + 12) + 9 = (3 + 15) * (5 / 2) = 45

공식화하면
· (price*1 + price*count) * count / 2 = price*(1 + count) * count / 2 = count * (count + 1) * price / 2
가 된다

※ 주의 사항은 조건의 최대 값을 고려해야한다.
· price : 1 ≤ price ≤ 2,500, price는 자연수
· count : 1 ≤ count ≤ 2,500, count는 자연수

조건에서 최댓값을 구하면 
· 2500 * 2501 * 2500 / 2 = 7,815,625,000

int 자료형을 넘어서기 때문에 int형으로 계산을 하면 잘못된 값이 나오게 된다.
- (signed) long (int) 4 byte -2,147,483,648 ~ 2,147,483,647
- unsigned long (int) 4 byte 0 ~ 4,294,967,295

그렇기 때문에 큰 자료형 (long long)으로 형변환이 필요하다.

 

using namespace std;
 
long long solution(int price, int money, int count)
{
    long long answer = -1;
 
    long long totalPrice;
    long long price_BigSize = (long long)price;
    long long money_BigSize = (long long)money;
 
    totalPrice = (count * (count + 1) * price_BigSize) / 2;
    
    answer = totalPrice - money_BigSize;
    if(answer < 0) {
        answer = 0;
    }
 
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓