백준 1789번 수들의 합 (JAVA, 그리디 알고리즘)

그리디 문제 풀던 중 기억해둬야 할 것 같아서 포스팅!
백준 문제들을 풀면서 두 정수 사이의 합 공식을 알고 있었고, 이 문제를 처음 풀 때 이 공식을 적용하려고 했었다.

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

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		long i = (long)Math.sqrt(n);
		while(true) {
			if(i*(i+1)>=n*2) break;
			i++;
		}
		System.out.println(i-1);
	}
}

x(x+1)=n^2라는 방정식은 떠올리고 적용하려 했다. Math.sqrt()를 통해 근사치를 찾고 i의 값을 증가시켜가며 해를 구하려 했지만, 1, 3 등이 입력되었을때 오답이 도출되었다. 더이상 이 코드를 발전시키기 어렵다는 생각이 들었고 고민 끝에 풀이를 찾아보았다.

풀이는 생각보다 간단했다. 아주 옛날에 배웠던 근의 공식을 이용하는 것이다. ax^+bx+c라는 방정식이 주어졌을 때, x= -b±Math.sqrt(b^2-4ac)/2a이다. 이를 적용한 코드는 다음과 같다.

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

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		int max = (int) ((-1+Math.sqrt(1+8*n))/2);
		System.out.println(max);
	
	}
}

알고리즘 문제를 풀기 위해 기초적인 수학 지식들을 습득해야 겠다.

그리고 따로 천천히 읽어보고 싶은 포스팅을 발견해서 링크 첨부.
알고리즘:1~n까지의 합을 구하는 원리