문제
접근
정말 어려운 문제였다.
앞에서 텀 프로젝트 문제를 푼 것이 크게 도움이 되었고, 해당 내용을 많이 사용하였다.
크게 두 단계로 구성된다.
첫 번째는 사이클을 검사하는 단계이다.
이 단계에서는 텀 프로젝트의 접근법을 기반으로 하여 조금만 추가하였다.
사이클에서 제외된 인원의 수를 구하는 것에 추가적으로 사이클을 구성하는 인원의 수도 구해주었다.
두 번째는 검출한 사이클들을 바탕으로 DP를 수행하는 단계이다.
DP는 배낭 문제와 거의 동일하다.
사이클의 수가 i, 탑승가능 인원이 j라고 할 때 DP의 구성은 다음과 같다.
DP(i, j)는 i 번째 사이클까지를 이용하여 최대 j명 까지 탑승할 수 있을 때, 최대 탑승가능 인원
즉 사이클이 3개가 나왔다고 할 때, DP(2, 5)는 1,2번 사이클을 사용해서 5명 이하의 최대 탑승인원을 나타낸다.
DP(i, j)를 구하는 방법은 조건이 많이 때문에 그냥 코드로 보자.
w는 i번째 사이클의 인원이고, r은 i번째 사이클에서 제외된 인원을 나타낸다.
코드
- 파이썬 코드
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
def dfs(v):
cycleMember = [v]
visit[v] = 1
group[v] = len(cycle)
while True:
if group[choice[v]] == -1:
group[choice[v]] = group[v]
else:
group[v] = group[choice[v]]
v = choice[v]
if visit[v] == 0:
visit[v] = 1
cycleMember.append(v)
else:
if v in cycleMember:
cycleStartIdx = cycleMember.index(v)
cycle.append(len(cycleMember) - cycleStartIdx)
notCycle.append(cycleStartIdx)
return
else:
notCycle[group[v]]+=len(cycleMember)
return
n, k = map(int, input().split(' '))
choice = [0] + list(map(int, input().split(' ')))
visit = [0] * (n+1)
cycle = []
notCycle = []
group = [0] * (n+1)
for i in range(1,n+1):
if visit[i] == 0:
dfs(i)
cycleCnt = len(cycle)
dp = [[0]*(n+1) for _ in range(cycleCnt+1)]
for i in range(1, cycleCnt+1):
w = cycle[i-1]
r = notCycle[i-1]
for j in range(1,n+1):
if w <= j:
dp[i][j] = w
if w+r >= j:
dp[i][j] = j
if dp[i-1][j-w] >= 0:
dp[i][j] = max(dp[i-1][j-w]+w, dp[i-1][j], dp[i][j])
else:
dp[i][j] = max(dp[i][j], dp[i-1][j])
else:
dp[i][j] = max(dp[i][j], dp[i-1][j])
ans = 0
for i in range(1,n+1):
if dp[cycleCnt][i] >= 0 and dp[cycleCnt][i] <= k:
ans = max(ans, dp[cycleCnt][i])
print(ans)