[백준 2903] 중앙 이동 알고리즘 - 자바(Java)

문제

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

2903번: 중앙 이동 알고리즘

 

 

초기 상태 점의 개수는 4 (2^2)

점을 1번 찍은 경우 점의 개수는 9 (3^2)

점을 2번 찍은 경우 점의 개수는 25 (5^2)이다.

이를 통해 규칙을 유추하면 쉽게 문제를 풀 수 있다.

 

점을 찍지 않은 상태에는 2의 제곱, 1번 찍었을 때는 3의 제곱, 2번 찍었을 때는 5의 제곱으로 점을 3번 찍었을 경우 (5 + 4)의 제곱인 81이 된다. 4번 찍었을 때는 (9 + 8) 제곱, ...

제곱의 증가하는 대상이 이전과의 차이가 1, 2, 4, 8, ...로 2배씩 증가한다.

 

코드

위 규칙을 통해 다음과 같은 코드를 작성할 수 있다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[16];
        int a = 2;
        int b = 1;

        for (int i = 1; i < arr.length; i++) {
            a += b;
            arr[i] = (int) Math.pow(a, 2);
            b *= 2;
        }

        System.out.println(arr[n]);
    }
}

 

 

 

 

 

 

거듭제곱을 활용하면 다음과 같이 코드를 작성할 수도 있다.

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println((int) (Math.pow(Math.pow(2, n) + 1, 2)));
    }
}