문제
놀이기구 이용료가 price, 처음 가진 금액이 money, 이용 횟수가 count일 때 총 필요한 금액에서 부족한 만큼을 구하는 문제임. 이용할 때마다 요금이 1배, 2배, 3배... 이런 식으로 늘어나는 게 포인트임.
처음 접근 - 반복문으로 그냥 다 더하기
일단 문제 조건부터 정리함.
- 이용료 1 ~ 2500
- 처음 가진 금액 1 ~ 1억
- 이용 횟수 1 ~ 2500
- 놀이기구 1번 이용료 = 이용 횟수 price (1번째는 price, 2번째는 2price...)
가장 단순하게 접근해서 1부터 count까지 돌면서 i * price를 누적하는 식으로 짬.
long total = 0;
for(int i=1; i<=count; i++){
total += i * price;
}여기서 total을 처음부터 long으로 잡았는데, 왜 그랬는지 스스로 명확히 설명은 못 했음. 그냥 "혹시 몰라서" 잡은 느낌.
시행착오 1 - i * price는 왜 오버플로우 걱정이 없는지
total은 long으로 잡았지만, i * price 자체는 int * int 연산임. 이 부분이 안전한지 직접 계산해봄.
i, price 둘 다 최대 2500이니까 2500 * 2500 = 6,250,000. int 최대 범위(약 21억)에 비하면 한참 작은 값이라 이 곱셈 자체는 오버플로우 걱정이 없다는 걸 확인함.
→ 즉 total을 long으로 잡은 건 최종 누적 합(total)이 커질 걸 대비한 거지, i * price 한 번의 곱셈 때문이 아니었음.
반복문 대신 수학 공식으로
반복문으로 1부터 count까지 다 더하는 대신, 등차수열 합 공식으로 한 번에 구할 수 있다는 힌트를 받고 손으로 확인해봄.
price = 100, count = 3 이라면
1*100 + 2*100 + 3*100 = 100 * (1+2+3)1+2+3 부분이 등차수열 합 공식 n(n+1)/2로 표현된다는 걸 떠올려서 아래처럼 씀.
long total = (count * (1 + count) / 2) * price;시행착오 2 - long으로 선언해도 오버플로우가 나는 이유
total을 long으로 선언했으니 당연히 안전할 거라고 생각했는데, 그게 아니었음.
우변 count * (1 + count) / 2 * price를 보면 count, price 전부 int 타입임. 왼쪽 변수 타입이 long이라고 해서 오른쪽 연산이 자동으로 long으로 바뀌는 게 아니라는 걸 몰랐음. 오른쪽 연산은 int끼리 다 끝난 다음에, 그 결과값만 long 변수에 대입되는 거였음.
직접 최댓값으로 계산해서 확인함 (count = price = 2500일 때):
count * (1+count)=2500 * 2501=6,252,500→ 아직 안전/ 2=3,126,250→ 아직 안전* price(2500) = 약 78억 →int최댓값(약 21억)을 훌쩍 넘음
즉 최종 곱셈 단계에서 이미 int 범위를 넘어버리고, 그 이후에 long total에 대입해봤자 이미 깨진 값이 들어가는 거였음.
시행착오 3 - 캐스팅 위치는 맞았는데 변수 타입을 놓침
오버플로우 지점을 찾고 나서 처음엔 이렇게 고침.
int total = (long)(count*(1+count)/2) * price;(long) 캐스팅 위치 자체는 맞았음. count*(1+count)/2가 오버플로우 나기 전 시점에 (long)으로 감쌌기 때문에, 그 뒤 * price부터는 자동으로 long 연산으로 승격됨.
근데 정작 왼쪽 total 변수를 다시 int로 선언해버림. 우변 결과는 이미 long(최대 78억짜리 값)인데, 이걸 int 변수에 담으려고 하니 타입이 안 맞는 문제가 생김. → total도 long으로 다시 고침.
최종 코드
class Solution {
public long solution(int price, int money, int count) {
long total = (long)(count * (1 + count) / 2) * price;
return total > money ? total - money : 0;
}
}배운 점
int * int연산은 각 값이 문제 조건상 작더라도, 이후 이어지는 연산(곱셈, 나눗셈 등)까지 감안해서 최댓값을 끝까지 손으로 계산해봐야 오버플로우 지점을 정확히 잡을 수 있음- 왼쪽 변수를
long으로 선언하는 것과, 오른쪽 연산이long으로 진행되는 것은 별개임. 오른쪽 연산 중 어느 한 값이라도(long)으로 캐스팅해야 그 지점부터 이후 연산이long으로 승격됨 - 캐스팅을 오버플로우 나기 전 지점에 넣어야 의미가 있음 (이미
int로 계산 끝난 뒤에 캐스팅해봤자 소용없음) - 반복 누적 로직을 수학 공식(등차수열 합 등)으로 치환할 수 있는지 항상 고려해볼 것 — 코드가 짧아지고 시간복잡도도 O(n)에서 O(1)로 줄어듦
