[백준] 1292번 쉽게 푸는 문제 자바(JAVA)

문제 : https://www.acmicpc.net/problem/1292

 

1292번: 쉽게 푸는 문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

---

정답 코드

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int firstIdx = Integer.parseInt(st.nextToken());
        int lastIdx = Integer.parseInt(st.nextToken());
        
        int res = sumOfSequence(lastIdx) - sumOfSequence(firstIdx-1);
        
        System.out.println(res);
    }
    
    
    public static int sumOfSequence(int num) {
        int res = 0;
        int i = 0;
        while(num - i > 0) {
            i++;
            num = num - i;
        }
        
        for(int j=1; j <= i; j++) {
            res += j*j;
        }
        res += (i + 1) * num;
        
        return res;
    }
}
 

 

수열의 구간 합을 구하는 문제

이중 for문을 돌려서 수열을 만들고 합을 구해도 되겠지만

(배열에 값 채우고 arr[n] 부터 arr[m] 까지 값 누적)

뭔가 재밌는 규칙을 찾아보고 싶었다

 

122333444455555... 이런 수열의 처음부터 n 번째 값까지의 합을 구하는 함수를 먼저 만들었다. 

그리고 n번째까지의 합에서 m-1번째까지의 합을 빼서 구간 합을 구했다. 

 

입력한 숫자에서 i++씩 뺀 값이 0보다 클 때까지 반복한다.

i 값 까지는 수열에서 같은 숫자가 같은 횟수 나온다. (ex. i=3이라면 12233344 --> 3이 3번 온전히 나옴)

i를 빼고 남은 num만큼 다음 숫자가 출력된다. 

(ex. i=4, num=3이라면  1223334444555 --> 5가 3번 나온다. )

 

그럼 num번째까지의 합은

(1*1 + 2*2 + 3*3 + ... + i*i) + (i+1) * num 이다!

 

알린이라 더 좋은 답이 있겠지만

카페 문닫는 시간 전에 풀어서 뿌듯하다 ㅎ.ㅎ