백준 2903 중앙 이동 알고리즘 / C++

문제 : 2903

풀이 point

점이 생기는 패턴을 파악해야한다. 점은 각 점 사이에 하나씩 끼워지면서 생기는 패턴이다.

초기 상태에서 1번으로 갈 때는 2개 사이에 점이 하나 생기므로 3이 됐다.
1번 상태에서 2번으로 갈 때는 2개 사이에 점이 총 2개 생기므로 5가 됐다.
2번 상태에서 3번으로 갈 때는 2개 사이에 점이 총 4개 생기므로 8이 됐다.

패턴은 바로 2의 제곱만큼 점이 추가 된다는 것이다.
세로도 가로와 같은 패턴이므로 점의 개수 * 점의 개수가 총 점의 개수가 된다.

풀이 방법

위의 발상을 통해 코드를 작성한다.

코드

//백준 2903, 중앙 이동 알고리즘
#include <iostream>

int main(){
    int N;
    int dp[16];
    std::cin >> N;
    dp[1] = 3; dp[2] = 5;
    int pow = 4;
    for(int i{3}; i<=N; ++i){
        dp[i] = dp[i-1] + pow;
        pow *= 2;
    }

    std::cout << dp[N] * dp[N];

    return 0;
}