[SWEA-5604] 구간 합

이 문제는 SWEA의 D4 레벨, [Professional] 구간 합 이라는 문제이다. 

 

이 곳을 클릭하면 문제 페이지로 이동합니다.

이 문제도 수업에서 다뤘던 내용인데, 선생님께서 식 안 알려주셨으면 무조건 틀렸을거다.

실제로 내 마음대로 풀었다가 시간초과 나서 실패했다.

import java.util.Scanner;

public class 구간합 {
	static long start, end;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			start = sc.nextLong();
			end = sc.nextLong();
			long ans = 0;
			
			for(long i=start; i<=end; i++) {
				String s = Long.toString(i);
				char[] ch = s.toCharArray();
				for(int j=0; j<ch.length; j++) {
					ans += ch[j] - '0';
				}
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
}

이 코드가 내 마음대로 풀었던 코드이다.

사실 숫자의 범위가 커서 무조건 안될 걸 알고 있었는데, 혹시나 하는 마음에 제출해 보았지만 역시나였다ㅎㅎ..

아마 숫자의 범위가 좀 작았다면 잘 돌아가지 않았을까 싶다.

이 코드를 조금 설명해보자면, 숫자를 string형태로 변환해서 toCharArray 를 이용해서 숫자를 하나씩 잘라서 더해주는 것이다.

 

이제 정답이 나왔던 코드의 로직을 설명해보자면,

가장 중요한 부분은 이 두 개의 수식이다. 이걸 그대로 구현하면 정답이다.

n은 현재 구하고자 하는 숫자를 나타내고 v는 자릿수를 나타낸다.

F(1) = 1, F(9) = 1+2+3+4+...+9 까지, F(11) = F(9) + 1+0+1+1 이다.

F(9)까지는 계산하기가 쉬운데, 10이나, 11, 23 등은 계산하기가 까다롭다.

 

숫자를 넣어서 생각을 해보면, 

F(11) = F(11-1-11%10)+G(11) = F(9)+G(11)

G(11) = 11/10*(11%10+1)+F(11%10) = 1*(1+1) +F(1) 이다.

즉, F(n) = F(a) + G(n) 에서  a 가 뜻하는 부분은 n보다 작은 가장 큰 9, 99, 999 등의 숫자이다.

G(n) 은 만약 n이 2자리 숫자라면 10 - n까지의 값을, 3자리 숫자라면 100-n까지의 값을 계산해 주는 것이다.

 

import java.util.HashMap;
import java.util.Scanner;

public class 구간합{
	static HashMap<Long, Long> f;
	static long start, end, ans;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		f = new HashMap<Long, Long>();

		long sum = 0;
		for(long i=0; i<10; i++) {
			sum += i;
			f.put(i, sum);
		}

		for(int tc=1; tc<=T; tc++) {
			start = sc.nextLong();
			end = sc.nextLong();
			
			if(start > 0)
				ans = F(end) - F(start-1);
			else 
				ans = F(end) - F(start);
			
			System.out.println("#"+tc+" "+ans);
		}	
	}
    
	static long F(long i) {
		if(f.containsKey(i)) return f.get(i);
		if(i<10) return f.get(i);
		
		long v = V(i);
		long F = F(i-1-i%v);
		long G = (i/v)*(i%v+1)+ F(i%v);
		long num = F+G;
		
		f.put(i, num);
		
		return num;
	}
	
	static long V(long i) {
		long v = 1;
		while(i>=10) {
			v = v*10;
			i = i/10;
		}
		return v;
	}
}

이 문제는 선생님께서 식을 알려주셔서 풀 수 있었던 것 같다.

근데 이런 식을 어떻게 생각해내셨을까.. 역시 나는 아직 가야할 길이 멀다..