swea 9843 촛불 이벤트

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR&categoryId=AXGBKzuaPOoDFAXR&categoryType=CODE

SW Expert Academy

 

 

N이 주어졋을때 이 N개의 촛불을 1 2 3 4 5 6 7 8 .. K 와 같은 방식으로 쌓을수있는지 판단하는 문제이다.

1~K 의 등차수열의 합은 K(K+1)/2이므로 K(K+1)/2 = N의 해를 구해주면된다.

완전 탐색으로는 N이 10^18 이므로 당연히 안되고 이분탐색을 이용하면 logN시간에 방정식의 해를 구할수 있다.

N의 입력값이 10^18까지 주어지기 때문에 적절한 left와 right 값을 정해줘야한다. ( 원칙상 right를 10^9보다 작은 값을 사용해야되지만 어차피 10^18이 long보다 훨씬 작기 때문에 나는 2^31-1인 Integer.MAX_VALUE를 사용했다.

 

package swea;

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

public class 양초이벤트 {
	public static class MyScanner{
        BufferedReader bf;
        StringTokenizer st;
        
         MyScanner(){
            bf = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st==null|| !st.hasMoreTokens()) {
                try{st = new StringTokenizer(bf.readLine());}
                catch(Exception e) {
                    e.printStackTrace();
                }
                
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int T = sc.nextInt();
		
		
		for(int tc=1;tc<=T;tc++) {
			
			long answer = -1;
			
			long N =sc.nextLong();
			
			long left = 0;
			long right = (1l<<31) -1;
			long middle = 0;
			while(left<=right) {
				middle = (left+right)/2;
				long t = (middle+1) *middle / 2;
				if(t==N) {
					answer = middle;
					break;
				}
				else if(t>N) {
					right = middle-1;
				}else left = middle+1;
				
			}
			
			
			
			System.out.printf("#%d %d\n",tc,answer);
			
			
		}
	}

}