[BAEKJOON]2903 중앙 이동 알고리즘

문제 요약

• 알고리즘 분류: 집합
• 난이도: Bronze3
• 문제내용:
  • 다음의 두 가지 규칙을 따릅니다:
    1. 각 변의 중앙에 점을 하나 추가
    2. 각 정사각형의 중심에 점을 하나 추가
  • N번 거친 후 점의 수를 출력해라
• 사이트: https://www.acmicpc.net/problem/2903

문제풀이

이 문제는 특정 패턴에 따라 그리드를 그릴 때 생성되는 점의 개수를 계산하는 알고리즘 문제입니다. 문제에서 보여주는 이미지를 통해 패턴을 이해할 수 있습니다.

패턴 분석

문제에서 주어진 패턴을 분석해보면:

1. N=1일 때, 2×2 사각형에 점 4개가 있습니다.
2. N=2일 때, 3×3 사각형에 점 9개가 있습니다.
3. N=3일 때, 5×5 사각형에 점 25개가 있습니다.
4. N=4일 떼, 9×9 사각형에 점 81개가 있습니다.

알고리즘은 다음과 같이 정의됩니다:

1. 정사각형의 각 변에 점을 하나 추가한다.
2. 정사각형의 중심에 점을 하나 추가한다.

수학적 규칙

각 단계별로 그리드의 크기와 점의 개수를 살펴보면:

1	2×2	4	(2^1 + 1)^2 = 3^2 = 9
2	3×3	9	(2^2 + 1)^2 = 5^2 = 25
3	5×5	25	(2^3 + 1)^2 = 9^2 = 81
4	9×9	81	(2^4 + 1)^2 = 17^2 = 289

여기서 패턴을 발견할 수 있습니다:

• N=1: 그리드 크기는 (2^1 + 1) = 3 (한 변에 점 3개)
• N=2: 그리드 크기는 (2^2 + 1) = 5 (한 변에 점 5개)
• N=3: 그리드 크기는 (2^3 + 1) = 9 (한 변에 점 9개)
• N=4: 그리드 크기는 (2^4 + 1) = 17 (한 변에 점 17개)

그리고 총 점의 개수는 그리드 크기의 제곱입니다.

일반화된 공식

N이 주어졌을 때, 점의 총 개수는:

 

(2^N + 1)^2

 

결론

이 문제는 패턴을 분석하고 수학적 공식을 도출하는 능력을 테스트합니다. 그리드의 성장 패턴을 분석하면 (2^N + 1)^2이라는 간단한 공식을 얻을 수 있으며, 이를 통해 어떤 N 값에 대해서도 효율적으로 점의 개수를 계산할 수 있습니다.

 

Code

Python

print((2 ** int(input()) +1) **2)

Java

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


public class Main {


	public static void main(String[] args) throws IOException {


		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		long N = Long.parseLong(br.readLine());

		System.out.println((long)Math.pow(Math.pow(2, N) + 1, 2));
	}

}

Javascript

var input = require('fs').readFileSync("/dev/stdin", "utf-8").trim();

console.log(Math.pow(Math.pow(2, input) + 1, 2));