[BOJ] 백준 1024 수열의 합

출처: https://www.acmicpc.net/problem/1024

Approach

L 길이를 가지는 (x, x+L]에 대해 수식을 세우면.

N = (x + 1) + ... + (x + L) 이다.

→ N = Lx + L * (L + 1) / 2

→ N - (L * (L + 1) / 2) = Lx

 

(좌항) N - (L * (L + 1) / 2) 이 L로 나누어 떨어지면 x를 구할 수 있다.

정달 출력시에는 x + 1 부터 x + L 까지 출력한다.

 

C++

#include <stdio.h>

int main()
{
	// freopen("input.txt", "r", stdin);
	int N, L;
	scanf("%d %d", &N, &L);
	
	for (int l = L; l <= 100; l++)
	{
		int tg = N - l * (l + 1) / 2;
		if (tg % l == 0) 
		{
			int x = tg / l + 1;
			if (x >= 0) 
			{
				for (int len = 0; len < l; len++) 
				{
					printf("%d ", len + x);
				}
				printf("\n");
				return 0;
			} 
		}
	}
	printf("-1\n");
}

 

Java

import java.util.Scanner;

public class Main {
	
	public static int func(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) {
		Scanner sc = new Scanner(System.in);
		int targetNum = sc.nextInt();
		int len = sc.nextInt();
		
		int start = 0;
		while(true){
			int temp = targetNum - func(len-1);
			if(temp < 0 || len > 100){  // 길이가 100보다 크거나 수열이 없을 때!  
				System.out.println(-1);
				return;
			}
			if(temp % len == 0){
				start = temp / len;
				break;
			}else{
				len++; // 최적의 길이를 탐색!  
			}
		}
		
		for (int i = start; i < start+len; i++) {
			System.out.format("%d ",i);
		}
	}
}