백준 1292번 : 쉽게 푸는 문제

 문제

www.acmicpc.net/problem/1292

1292번: 쉽게 푸는 문제

1292 쉽게 푸는 문제

 

 구현 방법

  구간합으로 구현하였습니다!  

단순하게 이중포문으로 구현할 수 있지만 이중포문은 시간복잡도가 O(n), 구간합의 시간복잡도는 O(1)이기 때문에 구간합을 사용해주었습니다. 해당 문제에서는 이중포문으로도 구현 가능합니다!

1은 1번, 2는 2번 3은 3번,.. 씩 더해줘야 하므로 카운트 변수를 만들어서 반복문 i=0 i<cnt i++ 해주고 반복문이 끝나면 카운트를 올려주었습니다.

모든 구간합을 더하고 입력된 구간의 시작을 끝으로 빼주었습니다.

 

 구현 코드

package BOJ.Silver.구현;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1292_쉽게푸는문제 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] dp = new int[1002];
		int index = 1, cnt = 1;
		while(index<1000) {
				for (int i=0;i<cnt;i++) {
						dp[index] = (dp[index-1]+cnt);
						index++;
						if (index>1001) break;
				}
				cnt++;
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		System.out.println(dp[end]-dp[start-1]);
	}
}

 

정답!