백준 2903 Java - 중앙 이동 알고리즘

제목 : 중앙 이동 알고리즘

---

문제

상근이는 친구들과 함께 SF 영화를 찍으려고 한다.

이 영화는 외계 지형이 필요하다.

실제로 우주선을 타고 와계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG 처리를 하려 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4 개를 고른다.

그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

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

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4 개의 정사각형이 새로 생긴다.

이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 총 2 번 거쳤을 때 까지의 모습이다.

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함 될 수 있다는 사실을 알았다.

메모리 소모량을 줄이기 위해서, 중복하는 점을 한 번만 저장하려고 한다.

과정을 N 번 거친 후, 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N 이 주어진다. ( 1 <= N <= 15 )

출력

첫째 줄에 과정을 N 번 거친 후, 점의 수를 출력한다.

예제 입력	예제 출력
1	9
2	25
5	1089

예제 입력, 출력 부분을 <pre> 태그로 작성하니, 만족스럽게 표현되서 기분이 좋다

---

맨 처음 알고리즘을 시작하면서 위의 문제를 접했을 때,

문제에서 자주 언급되는 정사각형 이라는 단어에 집중했던 기억이 있다.

또한, 메모리 소모량이 언급되며, "중복되는 점을 한 번만 저장" 이라는 문장에,

점의 개수는 어떠한 기준으로 구해야 하는지에 대해서 헷갈려 했다.

사실 지금 다시 문제를 봐도,

외계 지형을 구현하는 데 있어 증가된 점의 개수를 단순히 몇 개 저장해야 하는가를 구하는지 목적을 모르겠다 ㅋㅋ

하지만, 우리가 최종적으로 구해야 하는 것은, "점의 개수" 이다.

위의 사진에 제공된 예시를 보면, 하얀색과 검은색 점의 개수가 나타난다.

여기서 색상의 차이를 두지 말고,

주어진 N 번에 대하여 나타나게 된 점의 개수에 집중하자.

• 1 의 경우, 각 변의 점 개수는 3 개이다. 따라서, 점은 9 개다.
• 2 의 경우, 각 변의 점 개수는 5 개이다. 따라서, 점은 25 개다.

그렇다면, 3 이 주어졌을 때, 각 변의 점 개수는 몇 개가 될까?

바로 위의 문장이 키 포인트가 될 것이다.

현재 N 이 2 일 때, 변의 점 개수는 5 개이다.

이 때, 5 개의 점 사이에 1 개의 점을 추가한다면 총 몇 개의 점이 될까?

바로 9 개의 점이다.

여태까지 알아본 바에 이르면,

• 1 의 경우, 한 변의 점 개수는 3 - (출력 : 9)
• 2 의 경우, 한 변의 점 개수는 5 - (출력 : 25)
• 3 의 경우, 한 변의 점 개수는 9 - (출력 : 81)

이다.

즉, 현재 한 변의 점 개수는, 바로

(이전 상태의 점 개수 + 이전 상태의 점 개수 - 1) 이 되는 것이다.

각 점의 중앙에 새로운 점이 생기기 때문

중요한 것은, 주어진 N 에 따른 점의 개수를 구하기 위해서는,

이전 값을 필요로 한다는 것이다.

따라서, 답을 구하는 과정은 반복문을 통해서 해결하게 된다.

Answer

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 번 거친 후의 점 개수를 구하라 했으므로.
        int N = Integer.parseInt(br.readLine());

        // 한 번도 중앙 이동 알고리즘을 수행하지 않은 상태는, 한 변의 길이가 2 이다.
        // 그냥 순수 정사각형.
        int currPoint = 2;

        // 결과값 루프 시작
        for(int i = 0; i < N; i++) {
            // 현재 한 변의 점 개수는, 이전의 변 개수 + (이전 변 개수 - 1) 이다. - 중앙에 점 추가하므로
            currPoint = currPoint + (currPoint - 1);
        }

        System.out.println(currPoint * currPoint);
    }
}