COFO::1459B Move and Turn

• Link : COFO::1459B

Problem

• level : 1300
• tag : dp, math
• TIME
  • to understand : 5
  • to algorithm : 5
  • to code : 10
  • to debug : 60
  • understaing edit : 30

Point

• 원점에 말이 하나 있습니다.
• 이 말은 최초엔 상하좌우로 방향을 정할 수 있습니다.
• 1초마다 정해진 방향으로 이동후 왼쪽 혹은 오른쪽방향으로 방향을 틀 수 있습니다.
• 이때, n초 후에 해당 말이 있을 수 있는 점의 위치의 갯수는 몇개일까요

Design

• 수학적 증명 math 가 가능한 방법이 있을 거라고 생각했지만,
• 나이브한 bfs로 풀릴거라 생각했습니다.
• 하지만, n개의 bfs를 개별로 돌려야하므로(visit 처리 불가) TLE 를 맞게 됩니다.
• 이후, 5까지 그림을 그려가며 규칙을 찾았고, 이를 기반으로 dp 풀이하였습니다.
• 홀수번째 이동
  • 홀수번째 이동은 이전 홀수번째의 값과 이전 짝수번째 값을 통해 알아낼 수 있습니다.
• 짝수번째 이동
  • 짝수번째 이동은 제곱의 값을 갖는다는 것을 알아낼 수 있습니다.
• 위처럼 dp를 하는 방법은 결국 editorial 방법과 유사합니다.
• 일단 가로이동점의 갯수, 세로이동점의 갯수로 나누고 겹치는 부분이 몇개가 생길지에 대해서 생각해보면 규칙을 찾을 수 있습니다.

Complexity

• O(N)

Code

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
using namespace std;

int n;
unsigned long long ans[1001];
void solve(){
    cin >> n;
    ans[1] = 4, ans[2] = 4, ans[3] = 12, ans[4] = 9;
    unsigned long long cur = 4;
    rep(i, 5, n+1){
        if(i%2 == 0){
            ans[i] = cur * cur;
            cur++;
        }else ans[i] = ans[i-1] * 4 - ans[i-2];
    }
    cout << ans[n] << '\n';
}
int main(){
    //freopen("input.txt", "r", stdin);
    solve();
    return 0;
}