취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23256번 문제인 성인 게임이다.

문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/23256 

N이 2 이상일 때, 길이가 N-1인 칼날의 개수와 관련된 데이터를 이용하여 길이 N인 칼날의 개수를 구해보자.

길이가 N인 칼날은 다음과 같은 두 종류가 존재한다.

1. 왼쪽의 길이가 N-1인 부분칼날의 오른쪽에 세칸을 붙여 만들 수 있는 칼날

2. 1이 아닌 칼날: 오른쪽의 길이 1인 부분칼날(단, 길이 N-1인 부분칼날과 겹치는 칸은 1x1블럭으로 채워져있지 않다)과 나머지부분으로 생각할 수 있는 칼날

이 두 정보를 계속 저장해나가는 것으로 문제를 해결할 수 있다.

각 N에 대한 답을 모두 미리 구해두고, T개의 N에 대하여 답을 바로바로 출력해주자.

아래의 코드에서 A는 길이 N인 칼날의 개수, B는 길이 N인 칼날에서 맨 오른쪽 한칸이 빠진 칼날의 개수이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll A[1000001];
ll B[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	A[1] = 7, B[1] = 3;
	for (int i = 2; i <= 1000000; i++) {
		A[i] = (3 * A[i - 1] + 4 * B[i - 1]) % 1000000007;
		B[i] = (A[i - 1] + 2 * B[i - 1]) % 1000000007;
	}

	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << A[x] << '\n';
	}
}