[코딩테스트] 구간 합, 조합

• 모판을 만들어서 푸는 문제가 많이 나온다.
• 구간합을 미리 다 구해놓은 합 배열을 만든다.

 

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

 

 

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

public class BOJ1292_ans {
    public static void main(String[] args) throws IOException {
        int[] t = new int[1001];
        // 0, 1, 2, 2, 3, 3, 3 ...
        int idx = 1;
        for (int i = 1; i < 1001; i++) {
            for (int j = 0; j < i && idx < 1001; j++) {
                t[idx++] = i;
            }
        }

        int s[] = new int[1001];
        // 0, 1, 3, 5, 8, 11, 14...
        for (int i = 1; i < 1001; i++) {
            s[i] = s[i - 1] + t[i];
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(s[b] - s[a-1]);
    }
}

 

1000까지 미리 배열을 만들어 두어도 메모리 상 큰 차이는 없었다. 이렇게 하게 되면 값을 구할 때 O(1)로 구할 수 있다. 

 

https://www.youtube.com/watch?v=2OQTm2fTi50