def solution(a, b): return (a+b)*(abs(a-b)+1)/2
점화식으로 풀면 input의 크기에 무관하게 시간이 나온다. 식을 세울수 있으면 식으로 풀자. 계산도 간단하고 시간도 빠르다. 편의를 위해 작은 수를 a, 큰 수를 b라 하고 두 수를 포함하고 a~b사이 정수의 합을 S라 하면
2S 에서 (a+b)의 수는 (b-a)+1개 이므로 이다. 식을 정리하면 S는 위와같이 되는데 절대값을 이용해 a와 b의 값에 무관하게 식을 다음과 같이 정리할 수 있다.
위와 같은 방식에 의하여
를 리턴하면 위의 풀이와 같다.
function solution(a, b) {return (a+b)*(Math.abs(a-b)+1)/2;}
Javascript
같은 풀이
class Solution {public long solution(int a, int b) {return (long)(((double)(a+b)/2)*(Math.abs(a-b)+1));}}
class Solution {
public long solution(int a, int b) {
return (long)(((double)(a+b)/2)*(Math.abs(a-b)+1));
}
}
Java
같은풀이
위의 코드는 억지 한 줄 코드
Java
에서는 범위를 고려해야한다.
datatype | range |
---|---|
int | -2147483648 ~ 2147483647 |
long | -9223372036854775808 ~ 9223372036854775807 |
float | 1.4E-45 ~ 3.4028235E38 |
double | 4.9E-324 ~ 1.7976931348623157E308 |
이기 때문에 int
의 범위를 넘기 때문에 long
으로 해야한다.
2로 먼저 나누지 않으면 long
범위를 벗어나기 때문에 나누고 정수타입으로 두면 값이 변할 수 있기 때문에 double
로 바꾼다. 여기서 float
를 쓰게되면 범위를 벗어나는 테스트케이스가 존재하고 double
에서 계산 한 후에 최종 값을 long
으로 변환시켜 리턴한다.
Java
로 문제를 풀다보면 범위를 고려해야할 상황이 빈번하다. c
와 다르게 long long
도 없어서 범위도 더 좁고 BigInteger
를 사용해야 할 상황도 자주 있고 그만큼 불편하고 코드도 길어진다.
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
long long solution(int a, int b) {
return ((double)(a+b))/2*(abs(a-b)+1);
}
Java
와 유사하다 long long
이 있지만 여기서도 2로 먼저 나누지 않으면 범위를 벗어난다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
long long solution(int a, int b) {
return ((double)(a+b))/2*(abs(a-b)+1);
}
C++
하고 거의 똑같다.
def solution(a, b): return (a+b)*(max(a,b)-min(a,b)+1)/2
풀이1에서 절대값을 사용하지 않고 최대와 최소를 이용하면
이므로 를 리턴하면 같은식이다.
def solution(a, b): return sum(range(min(a,b),max(a,b)+1))
풀이2에서 점화식을 이용하지않고
의 정수 범위를 더하는 식이다. 점화식이 생각나지 않는다면 이러한 방식으로 풀면된다. 수의 범위를 n이라 하면 모든 값을 더하기 때문에 시간이 걸리므로 풀이1,2 보다 느리다.