https://www.acmicpc.net/problem/14238
14238번: 출근 기록
스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의
www.acmicpc.net
dp[a][b][c][pre1][pre2]: 현재까지 A, B, C가 각각 a, b, c번 출근하였고, 전날 출근을 pre1, 전전날 출근을 pre2가 했을 때 올바른 출근 기록인지 여부
1일마다 A, B, C 중 한 명이 무조건 출근하며
A: 매일 출근할 수 있다.
B: 출근한 다음날은 반드시 쉬어야 한다.
C: 출근한 다음날과 다다음날은 반드시 쉬어야 한다.
위 조건들을 이용해서 구현 해야 합니다.
리턴 받은 값이 1이면 올바른 출근기록이므로 순서대로 출력해주시면 됩니다.
0을 리턴받았으면 올바른 출근기록이 없으니 -1을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 51
using namespace std;
string str;
int dp[MAX][MAX][MAX][3][3];
int cnt[3];
int N;
int dfs(int a, int b, int c, int pre1, int pre2) {
if (a + b + c == N) return 1;
int &ret = dp[a][b][c][pre1][pre2];
if (ret != -1) return ret;
ret = 0;
if (a < cnt[0]) {
ret = dfs(a + 1, b, c, 0, pre1);
if (ret == 1) {
cout << 'A';
return ret;
}
}
if (b < cnt[1]) {
if (pre1 != 1) {
ret = dfs(a, b + 1, c, 1, pre1);
if (ret == 1) {
cout << 'B';
return ret;
}
}
}
if (c < cnt[2]) {
if (pre1 != 2 && pre2 != 2) {
ret = dfs(a, b, c + 1, 2, pre1);
if (ret == 1) {
cout << 'C';
return ret;
}
}
}
return ret;
}
void func() {
memset(dp, -1, sizeof(dp));
if (!dfs(0, 0, 0, 0, 0)) cout << "-1\n";
}
void init() {
N = str.size();
for (int i = 0; i < N; i++) {
cnt[str[i] - 'A']++;
}
}
void input() {
cin >> str;
init();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12978 스크루지 민호 2 (0) | 2022.06.08 |
|---|---|
| boj 10986 나머지 합 (0) | 2022.03.08 |
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |