[JAVA] [SWEA] 9843. 촛불 이벤트

당신은 프로포즈를 위해 촛불을 삼각형으로 배치하고 있다. 촛불을 K단 크기로 배치하면, 1단에는 K개의 양초, 2단에는 K-1개의 양초, …, K단에는 1개의 양초를 배치해서 총 (K(K+1))/2개의 양초가 필요하다.

당신이 사용할 양초의 개수 N이 주어질 때, 이 양초를 모두 사용하면 몇 단 크기의 촛불 삼각형을 만들 수 있는지 구하여라.

 

처음에 문제만 읽었을때 만들수 있는 촛불의 단이 최대 몇인지 구하는 것인지 알고 잠깐 고민했으나

 

각 테스트 케이스 마다 주어진 양초 N개를 모두 사용하여 만들 수 있는 촛불 삼각형의 단수를 출력한다. 만약 삼각형을 만드는 것이 불가능하면 -1을 출력한다.

 

출력에 이렇게 함정을 놔두어 헷갈리게 해두었다...

 

나만 그렇게 느끼나 처음에 문제만 보면 최대 몇개 만들 수 있는지로 이해했었는데... ㅠㅠ

 

여튼 문제는 매우 단순하다 이거는 D5라기 보다는 수학을 이해하면 D3 정도로 낮아질 수가 있다.

 

결국 1단부터 K단까지 쌓게되면 위에 공식처럼 K(K+1)/2 가되는데 

 

K(K+1)/2 = N 이라 할때 우리는 N을 받기 때문에

 

K(K+1) = 2N이 되고 약간 계산하기 편하게 하여

 

K^2 = 2N ---> K = route(2N) 이라고 보면 K의 최소값을 알 수 있다.

 

K(K+1) >= K^2 이기 때문에 이때 구한 K부터 1씩 증가시켜보면서 확인 절차도 해볼 것이다.

 

증가시키더라도 K+a단 쌓았을 때 N이 넘어가면 그만확인해보면 해결이 가능하다.

 

전체 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; ++t) {
			long num = Long.parseLong(br.readLine());
			long result = 0;
			long index = -1;
			for(long n=(long)Math.sqrt(num*2); ; ++n) {
				result = (n*(n+1))/2;
				if( result == num ){
                    index = n;
                    break;
                }else if( result > num ){
                    break;
                }
				
			}
			bw.write("#"+t+" "+index+"\n");
		}
		br.close();
		bw.close();
	}

}