[알고리즘][X] [Professional] 구간 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo&

SW Expert Academy

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

public class Solution {
	static StringBuilder sb = new StringBuilder();
	static HashMap<Long, Long> dp = new HashMap<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for (int testCase = 1; testCase <= T; testCase++) {
			st = new StringTokenizer(br.readLine());
			long A = Long.parseLong(st.nextToken());
			long B = Long.parseLong(st.nextToken());
			
			long sum = 0;
			for (long i = 0; i < 10; i++) {
				sum += i;
				dp.put(i, sum);
			}
			
			long a = accSum(A-1);
			long b = accSum(B);
			sb.append("#").append(testCase).append(" ").append(b-a).append("\n");
		}
		System.out.println(sb);
	}

	private static long accSum(long n) {
		if (dp.containsKey(n)) {
			return dp.get(n);
		}
		if (n < 10) {
			return n * (n+1) / 2;
		}
		String s = String.valueOf(n);
		long v = (long) Math.pow(10, s.length()-1);
		long num = accSum(n - 1 - n % v) + n / v * (n % v + 1) + accSum(n % v);
		dp.put(n, num);
		return num;
	}
	
}

나의 풀이

- 식을 활용해서 풀면 된다.

- 다만 StackOverflow 문제가 터졌는데 long으로 하지 않아서 + v를 int로 형변환해주어서 였다.

- 주의하자!!!!