[백준] 2903번: 중앙 이동 알고리즘

https://www.acmicpc.net/problem/2903

2903번: 중앙 이동 알고리즘

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int width = 3;
		int[] star = new int[16];
		for(int i=1; i<star.length; i++) {	// 1 ~ 15
			star[i] = width * width;
			width = width + (width-1);
		}
		
		System.out.println(star[N]);
		scan.close();
	}
}

 

풀이

규칙만 찾으면 쉽게 해결 할 수 있다.

저장해야하는 점의 개수는 제곱수이다.

9 -> 25 -> 81 -> 289 -> ...

따라서 몇의 제곱인지만 찾아주면 된다.

 

가로의 점의 개수를 보면(N = 1부터)

3, 5, 9, 17, 33, ...가 된다

3 = 2 + (2-1)

5 = 3 + (3-1)

9 = 5 + (5-1)

17 = 9 + (9-1)

33 = 17 + (17-1)

...

 

위와 같이 이전 숫자 + (이전 숫자-1) 의 규칙이 있다.

N의 크기가 15밖에 안되므로 배열에 모든수를 구하고, 입력받는 인덱스의 값을 출력했다.