백준 14651번 걷다보니 신천역 삼(Large)

문제 링크입니다: https://www.acmicpc.net/problem/14651

백준 14650번 걷다보니 신천역 삼(Small)(http://jaimemin.tistory.com/774)와 달리 단순 브루트 포스로는 풀 수 없는 문제였습니다.

DP(Dynamic Programming)을 적용시킬 수 없을까라고 생각하는 와중에 단순한 점화식이 보였습니다.

점화식은 아래와 같습니다.

1. 길이가 1일 때는 0, 길이가 2일 때는 2, 길이가 3일 때는 6, 길이가 4일 때는 18, ...

2. 따라서 cache[2]=2로 저장하고 길이가 3일 때부터 cache[i]=(cache[i-1]*3) % MOD 연산을 통해 계산하면 되는 문제였습니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 33333 + 1;

const int MOD = 1000000009;

 

int N;

long long cache[MAX]; //(0, 1, 2), length

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

        //cache[1]=0

        //cache[2]=2

        //cache[3]=6

        //cache[4]=18

        cache[2] = 2;

 

        for (int i = 3; i <= N; i++)

                 cache[i] = (cache[i - 1] * 3) % MOD;

        cout << cache[N] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~