[SWEA / Java] 9843번: 촛불 이벤트 (D5)

문제 풀이 날짜: 2023.08.11
포스트 작성일: 2023.08.21

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 9843번: 촛불 이벤트 (D5)

 

키워드

수학

 

풀이 접근법

• 공차가 1인 등차수열의 합 공식을 응용하는 문제이다.
• 문제는 이렇게도 설명 가능하다: k(k+1) = 2N 이다. N이 주어졌을 때 k를 구하시오.
• 문제의 입력이 10^18까지이므로 최소 O(√n)시간 이하로 풀이해야 한다. (그 이상은 시간 초과)
  • 만약 10^18개의 수보다 적은 양을 조사해서 k를 구하고 싶다면 어떻게 해야 할까?
  • 다음과 같은 식을 통해 k의 최대치를 알아낼 수 있다. sqrt() 함수로 k값을 구하고 공식에 넣어 검증해보면 된다.

유도 과정

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			long answer = -1;
			
			long N = Long.parseLong(br.readLine());
			
			if(N == 1) {
				sb.append("#").append(test_case).append(" ").append(1).append("\n");
				continue;
			}
			
              //k값은 최대 √n이다.
			long k = (long) Math.sqrt(2 * N);
			if(k * (k + 1) / 2 == N) { //만약 k를 넣어서 공식이 성립한다면
					answer = k; //그것이 답이 된다.
			}
            
			sb.append("#").append(test_case).append(" ").append(answer).append("\n");
		}
		
		System.out.print(sb);
	}

}

---

야매로 풀긴 했지만, 수학적 원리를 이용해서 푸는 문제이기 때문에 구현할 코드는 사실상 별로 없다. 이 외에도 수학적인 성질을 이용하면 O(1)시간만에 풀이할 수 있는 문제가 꽤 있으니 신경써보는 게 좋겠다.

 

git 링크

(git 링크 첨부)