백준14651 걷다보니 신천역 삼

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14651

문제 출처

  • 제1회 천하제일 코딩대회 본선 A, B번

사용 알고리즘

  • DP

시간복잡도

  • O(n)

풀이

1이 입력되면 정답은 0
2가 입력되면 정답은 2
3이 입력되면 정답은 6
4가 입력되면 정답은 18
…
10이 입력되면 정답은 13122입니다.

점화식을 세워봅시다.
f(1) => 0
f(2) => 2
else => f(i) = A(i-1) * 3 입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

typedef long long ll;
int mod=1e9+9;

int main(){
	int n;
	scanf("%d", &n);
	ll dp[40000] = {0, 0, 2, };
	for(int i=3; i<=n; i++) dp[i] = dp[i-1] * 3 % mod;
	printf("%lld", dp[n] % mod);
}