3948 홍준이의 친위대

백준 3948 홍준이의 친위대 https://www.acmicpc.net/problem/3948

<유사문제>
1146 지그재그 서기 https://www.acmicpc.net/problem/1146

1. 맨 앞줄에는 아무나 설 수 있다.
2. 둘째 줄에도 아무나 설 수 있다.
3. 셋째 줄에는 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 클 경우, 둘째 줄에 서 있는 사람보다 작은 사람만이 설 수 있으며, 둘째 줄에 서 있는 사람이 첫째 줄에 서 있는 사람보다 작을 경우, 둘째 줄에 서 있는 사람보다 큰 사람만이 설 수 있다.
4. 넷째 줄부터는 둘째 줄과 셋째 줄을 비교하는 식으로 해서 N번째의 줄을 서는 사람은 N-2번째 줄과 N-1번째 줄에 서는 사람을 비교해서 세운다.

N명의 학생이 존재할 때 다음의 규칙을 따른다. 사실 이 말은 지그재그로 학생을 배치하는 것이다.

문제는 학생의 위치를 저장할 때 bitmask dp나 방문배열로 확인할 수 가 없다. (N이 100이하이므로)

그래서 다른 방법으로 접근해야하는데 바로 현재상태에서 작은사람과 큰사람의 수를 저장하며 비교하는것이다.

#include <cstdio> #include <cstring> #define mod 1000000 int N; int dp[111][111][2]; // 현재 사람보다 작은사람이 S, 큰사람이 L명 있을 때  // flag(1 : 더 큰사람을 골라야하는 경우, 0 : 더 작은 사람을 골라야하는 경우) int solve(int L, int S, int flag){             int range = L + S;     if (range == 0) return 1;          int &ret = dp[L][S][flag];     if (ret != -1) return ret;     ret = 0;     if (!flag)        //S을 골라야함         for (int i = 0; i < S; i++)             ret += solve(range - (i + 1), i, 1), ret %= mod;     else         for (int i = 0; i < L; i++)             ret += solve(i, range - (i + 1), 0), ret %= mod;     return ret % mod; } int main(){     memset(dp, -1, sizeof(dp));     scanf("%d", &N);     if (N == 1){         printf("1\n");         return 0;     }     int ans = 0;     for (int n = 0; n < N; n++){         ans += solve(n, N - 1 - n, 0);         ans %= mod;         ans += solve(n, N - 1 - n, 1);         ans %= mod;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs