[SWEA] 8016. 홀수 피라미드

문제

경표는 아래와 같이 삼각형 모양으로 숫자를 쌓기로 했다.

1층에는 1개, 2층에는 3개, 3층에는 5개, … 와 같이 쌓는다.

위와 같이 경표는 끝도 없이 피라미드를 쌓을 때, N층의 제일 왼쪽, 오른쪽에 쓰게 될 숫자가 무엇일지 예측해보자.

 

풀이방법

처음에는 동적계획법(DP, Dynamic Programming) 알고리즘을 사용해 풀었으나 제출 시에 시간초과가 발생했다.

 

이유는 입력으로 n이 최대 10^9까지 입력되는데 이럴 경우 반복문은 1,000,000,000을 돌아야하므로 시간초과가 발생한다.

 

다른 방법으로 접근하면 왼쪽 가장자리의 수와 오른쪽 가장자리의 수들을 일정한 규칙을 가지는 수열로 생각하는 것이다.

 

왼쪽 가장자리 : 1, 3, 9, 19, ....

 

오른쪽 가장자리 : 1, 7, 17, 31, ...

 

그러면 왼쪽 가장자리는 n층일 때, 2 X (n-1) X (n-1) + 1이 되고

 

오른쪽 가장자리는 n층일 때, 2 X n X n - 1이 된다.

 

소스코드

package samsung;

import java.util.*;

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