문제 : https://www.acmicpc.net/problem/1292
1292번: 쉽게 푸는 문제
첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.
www.acmicpc.net
동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.
이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.
하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.
정답 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | 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; } } | cs |
수열의 구간 합을 구하는 문제
이중 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 이다!
알린이라 더 좋은 답이 있겠지만
카페 문닫는 시간 전에 풀어서 뿌듯하다 ㅎ.ㅎ
'발전 > JAVA' 카테고리의 다른 글
[백준] 1049 기타줄 JAVA 자바 해설 및 정답코드 (0) | 2022.04.07 |
---|---|
[백준] 1002 터렛 풀이, 정답코드, 채점결과 (0) | 2022.01.31 |
[백준]1010번 다리놓기 풀이 코드/입출력 방식에 따른 성능 개선 (0) | 2022.01.31 |
[java] BigInteger (java.math) - 백준 1271번, 2338번 (0) | 2021.09.11 |
[Java] 큰 따옴표(" ")와 작은 따옴표(' ') 차이 (1) | 2021.07.14 |