취미로 코딩하기

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

이번에 볼 문제는 백준 11369번 문제인 Safe Zone이다.
문제는 아래 링크를 확인하자.

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

무조건 K번 양 옆으로 움직인 뒤 [P, Q] 안에 들어온 경우의 수를 계산해야 하므로 매 움직임 이후 각 장소에 서있게 될 경우의 수를 DP를 통하여 계산하자.

문제의 각 변수의 범위가 정해져있지 않은데, 글쓴이는 문제의 답이 int범위 내로 들어오고, N는 1000 이하로 들어온다는 가정 하에 코드를 작성하였다.

memset의 시간이 오래 걸릴 것을 대비해 toggling DP로 구현하였다.

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

#include <iostream>
#include <cstring>
using namespace std;

int N, P, Q, J, K;
int dp[1002][2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	while (cin >> N >> P >> Q >> J >> K) {
		if (N == 0) break;
		memset(dp, 0, sizeof(dp));
		dp[J + 1][0] = 1;
		for (int k = 1; k <= K; k++) {
			for (int i = 1; i <= N; i++) {
				dp[i][k & 1] = dp[i - 1][(k & 1) ^ 1] + dp[i + 1][(k & 1) ^ 1];
			}
		}
		int ans = 0;
		for (int i = P + 1; i <= Q + 1; i++) {
			ans += dp[i][K & 1];
		}
		cout << ans << '\n';
	}
}