[SW Expert Academy] - (D3)8016. 홀수 피라미드

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

SW Expert Academy

틀린 코드(시간 초과)

import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int t = scan.nextInt();
		for(int tc=1; tc<=t; tc++) {
			int n = scan.nextInt();
			int leftSeq = 2;
			int rightSeq = 2;
			int leftNum = 1;
			int rightNum = 1;
			if(n == 1) {
				System.out.println("#" + tc + " 1 1");
				continue;
			}
			
			// N층의 제일 왼쪽
			for(int i=0; i<n-1; i++) {
				leftNum += leftSeq;
				leftSeq += 4;
			}
			
			// N층의 제일 오른쪽
			for(int i=0; i<n; i++) {
				rightNum += rightSeq;
				rightSeq += 4;
			}
			
			System.out.println("#" + tc + " " + leftNum + " " + (rightNum-2));
			
		}
		
		scan.close();
	}

}

 으음 문제를 보고 가장 먼저 규칙을 찾아야겠다는 생각이 들었다. 그래서 규칙을 찾아보았다.

각 층별로 젤 왼쪽값을 보자.

1   3   9   19   33   51 ...

약간 수학적인 문제로 규칙은 다음과 같이 더해진다.

각 항마다 2, 6, 10, 14, 18, ... 4씩 커지면서 더해진다. (계차 수열)

왼쪽값은 위와 같이 구할 수 있고, 가장 오른쪽 값은 그 다음층의 젤 왼쪽값에서 -2를 하면 된다.

 

1   7   17   31   49   71 ...

위 숫자들도 마찬가지로 계차수열로 4씩 커지지만, 그냥 다음층의 젤 왼쪽값을 구한 뒤 -2를 해주면 된다.

 

따라서 젤 왼쪽값은 처음엔 2를 기준으로, 입력받은 층(n)의 -1만큼 4씩 더하는 규칙을 통해 찾으면 되고,

젤 오른쪽값은 위와는 동일하게 입력받은 층(n) 까지 4씩 더하는 규칙으로 찾고 -2를 하면 된다.

 

하지만 제출해보니 시간 초과가 발생했다... 왜?

문제에서 자세히보면 n의 범위는 10^9승 이다.... 이 값은 10억으로 당연히 시간 초과가 발생할 수 밖에 없다...

(보통 시간을 계산할때, 1억의 범위가 1초라고 판단하면 된다... 즉 10억이면 대략 10초정도 걸린다.)

따라서 for문 자체를 사용하면 안된다!!!

 

그럼 다른 규칙을 찾아야 한다.... 뭔가 알고리즘이지만 수학적인... 평소에도 규칙찾는걸 좋아하던 터라 어렵지는 않았다.

각 항들에대해 -1, +1 등을 해보고 규칙을 끼워맞추면서 찾았다.

 

젤 왼쪽층의 규칙은 (n-1) * (n-1) * 2 + 1 이다... (음 대입해보면 답이 나온다...^^;;)

젤 오른쪽의 규칙은 (n*n*2) - 1 이다.

이렇게 하면 시간복잡도는 O(1)이 되고, 시간 초과가 발생하지 않는다!

 

 

따라서 정답코드는 다음과 같다.

import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int t = scan.nextInt();
		for(int tc=1; tc<=t; tc++) {
			long n = scan.nextLong();
			long leftNum = (n-1) * (n-1) * 2 + 1;
			long rightNum = (n*n*2) - 1;
			System.out.println("#" + tc + " " + leftNum + " " + rightNum);
		}
		
		scan.close();
	}

}