백준 1024

• 실버 2단계 문제

풀이)

어떤 수들의 합 = N이 되려면 어떤 수들 중 가장 작은 수는 N/L을 넘지 말아야 한다.

예를 들어 18, 4에 대해
18/4 = 4를 기준으로
4567 3456 2345 1234. 의 배열을 만들 수 있다.

1. 만약 4567의 합이 18보다 크면 3456을, 3456의 합이 18보다 크면 2345를 비교하면서 기준값을 1씩 뺀다.

2. 만약 4567의 합이 18이면 return한다.

3. 4567의 합이 18보다 작으면 L이 4인 경우는 18을 만들 수 없으므로 L을 1 늘린다.
   그럼 만들어지는 배열은
   34567 23456 12345 ... 이다.

• 만약 기준값이 1인데 1~L의 합이 18보다 크면 18을 만드는 게 불가능하므로 -1 출력.
• 만약 L이 100을 넘으면 -1 출력.

내 코드)

import java.io.*;
import java.util.*;

public class Backjoon1024 {
	
	static void calc(int N, int L) {
		StringBuilder sb = new StringBuilder();
		int mid = N/L;
		while(true) {
			int sum = 0;	
			for(int i=0;i<L;i++) {
				sum += (mid + i);
			}
			
			if(N < sum) {
				mid--;
				if(mid<0) {
					System.out.println(-1);
					return;
				}								
			}else if (N==sum) {
				for(int i=0;i<L;i++) {
					sb.append((mid+i) + " ");
				}
				System.out.println(sb);
				return;
			}else {
				L++;				
			}
			if(L>100) {
				System.out.println(-1);
				return;
			}
		}
	}
	
	public static void main(String[]args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());

		calc(N, L);
	}
}

다른 코드)

위의 방식은 시간이 너무 많이 걸려서 다른 방법을 찾아보았다.
N = (x+1) + (x+2) + .. (x+y) = y*x + y(y+1)/2 이다.
즉, N-y(y+1)/2가 y로 나눠지면 x를 구할 수 있다.

import java.io.*;
import java.util.StringTokenizer;

public class main {
	
	static int calc(int k){//등차수열의 합   
		if(k == 0)
			return 0;
		else if(k == 1)
			return 1;
		int sum = k * ( k + 1);
		return sum / 2;
		
	}
	public static void main(String[] args) throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		
		int start = 0;
		while(true){
			int temp = N - calc(L-1);
			if(temp < 0 || L > 100){  // 길이가 100보다 크거나 수열이 없을 때!  
				System.out.println(-1);
				return;
			}
			if(temp % L == 0){
				start = temp / L;
				break;
			}else{
				L++; // 최적의 길이를 탐색!  
			}
		}
		
		for (int i = start; i < start+L; i++) {
			System.out.format("%d ",i);
		}
	}
}