DP 알고리즘 문제를 풀다가, 문득 '로스트아크 세공도 DP로 확률을 구할 수 있지 않을까?' 싶어서 관련 내용을 찾아봤다. 그리고,
https://www.inven.co.kr/board/lostark/4821/82409
등의 글을 참고해보니, 된다고 하더라. 그래서 스스로 아이디어를 짜서 코드를 짰다.
(내가 아는 선에서) 기본적인 규칙 (개인적으로 로스트아크는 1시간 해본게 끝이다. 아님 말고)
- 3개의 어빌리티 스톤이 있으며, 2개는 성공하면 능력치 증가, 1개는 성공하면 능력치 감소이다.
- 어빌리티 스톤마다 10번의 시도 기회가 있다.
- 유저는 스톤1, 스톤2, 스톤3 중 하나를 선택하여 강화를 시도할 수 있다.
- 성공 확률은 처음에 75%이며, 성공할 때마다 10%p씩 감소하여 최저 25%까지 내려가며, 반대로 실패할 경우 10%p씩 증가하여 최대 75%까지 올라간다.
- 목표는 유저마다 다르다. but 일반적으로 77돌(스톤1, 스톤2에서 7번 이상 성공)을 노리고, 97돌(스톤1 or 스톤2에서 9번, 7번 이상 성공)은 부자의 flex 내지 스트리머들의 재롱잔치 정도의 의미를 갖는 듯하다. 스톤3의 성공 횟수를 일정 숫자 아래로 내리는 것도 목표인 듯한데, 자세히는 모른다.
- 아래 코드의 목표는, 주어진 상태별로 스톤1 성공 횟수 + 스톤2 성공 횟수 >= 16일 확률을 구하는 것이다.
참고: https://www.youtube.com/watch?v=wN0gxMvzjEc
함수 f(a,b,c,d,e,f,g)에는 현재 상태를 입력해주면 되는데,
- a: 스톤1 실패 횟수(0=<a=<4: 실제로는 10번까지 실패할 수 있지만, 97돌 알고리즘 짜는 입장에서 고려할 필요가 없음.)
- b: 스톤1 강화 시도 횟수(0=<b=<10)
- c: 스톤2 실패 횟수
- d: 스톤2 강화 시도 횟수
- e: 스톤3 실패 횟수(0=<e=<10)
- f: 스톤3 성공 횟수
- g: 확률(0<=g<=5, 현재 시도의 확률 p% == (25 + 10*g)%)
초기값은 f(0,0,0,0,0,0,5)가 된다.
코드
"""
a: 첫 번째 돌 실패 횟수
b: 첫 번째 돌 시도 횟수
c: 두 번째 돌 실패 횟수
d: 두 번째 돌 시도 횟수
e: 세 번째 돌 실패 횟수(디버프 돌의 성공(=디버프 활성화)은 성공으로 간주함. 즉, 실패해야 좋음)
f: 세 번째 돌 시도 횟수
g: 확률 보정(g==0~5, g==0: 25%, g==5: 75%)
"""
dp = [[[[[[[None]*6 for _ in range(11)] for _ in range(11)] for _ in range(11)]
for _ in range(5)] for _ in range(11)] for _ in range(5)]
def func(a, b, c, d, e, f, g):
# print(a,b,c,d,e,f,g)
if (b+d) - (a+c) >= 16:
dp[a][b][c][d][e][f][g] = 1
return 1
if a+c>= 5:
return 0
if dp[a][b][c][d][e][f][g] != None:
return dp[a][b][c][d][e][f][g]
if b == 10: # 첫 번째 돌 기회 다 씀
if f == 10: # 세 번쨰 돌 기회 다 씀
p = 0.25 + 0.1*g
if p == 0.25:
dp[a][b][c][d][e][f][g] = p*func(a,b,c,d+1,e,f,g)+(1-p)*func(a,b,c+1,d+1,e,f,g+1)
return dp[a][b][c][d][e][f][g]
elif p == 0.75:
dp[a][b][c][d][e][f][g] = p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g)
return dp[a][b][c][d][e][f][g]
else:
dp[a][b][c][d][e][f][g] = p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g+1)
return dp[a][b][c][d][e][f][g]
else:
p = 0.25 + 0.1*g
if p == 0.25:
dp[a][b][c][d][e][f][g] = max(p*func(a,b,c,d+1,e,f,g)+(1-p)*func(a,b,c+1,d+1,e,f,g+1),
p*func(a,b,c,d,e,f+1,g)+(1-p)*func(a,b,c,d,e+1,f+1,g+1))
return dp[a][b][c][d][e][f][g]
elif p == 0.75:
dp[a][b][c][d][e][f][g] = max(p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g),
p*func(a,b,c,d,e,f+1,g-1)+(1-p)*func(a,b,c,d,e+1,f+1,g))
return dp[a][b][c][d][e][f][g]
else:
dp[a][b][c][d][e][f][g] = max(p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g+1),
p*func(a,b,c,d,e,f+1,g-1)+(1-p)*func(a,b,c,d,e+1,f+1,g+1))
return dp[a][b][c][d][e][f][g]
if d == 10: # 두 번째 돌 기회 다 씀
if f == 10: # 세 번쨰 돌 기회 다 씀
p = 0.25 + 0.1*g
if p == 0.25:
dp[a][b][c][d][e][f][g] = p*func(a,b+1,c,d,e,f,g)+(1-p)*func(a+1,b+1,c,d,e,f,g+1)
return dp[a][b][c][d][e][f][g]
elif p == 0.75:
dp[a][b][c][d][e][f][g] = p*func(a,b+1,c,d,e,f,g-1)+(1-p)*func(a+1,b+1,c,d,e,f,g)
return dp[a][b][c][d][e][f][g]
else:
dp[a][b][c][d][e][f][g] = p*func(a,b+1,c,d,e,f,g-1)+(1-p)*func(a+1,b+1,c,d,e,f,g+1)
return dp[a][b][c][d][e][f][g]
else:
p = 0.25 + 0.1*g
if p == 0.25:
dp[a][b][c][d][e][f][g] = max(p*func(a,b+1,c,d,e,f,g)+(1-p)*func(a+1,b+1,c,d,e,f,g+1),
p*func(a,b,c,d,e,f+1,g)+(1-p)*func(a,b,c,d,e+1,f+1,g+1))
return dp[a][b][c][d][e][f][g]
elif p == 0.75:
dp[a][b][c][d][e][f][g] = max(p*func(a,b+1,c,d,e,f,g-1)+(1-p)*func(a+1,b+1,c,d,e,f,g),
p*func(a,b,c,d,e,f+1,g-1)+(1-p)*func(a,b,c,d,e+1,f+1,g))
return dp[a][b][c][d][e][f][g]
else:
dp[a][b][c][d][e][f][g] = max(p*func(a,b+1,c,d,e,f,g-1)+(1-p)*func(a+1,b+1,c,d,e,f,g+1),
p*func(a,b,c,d,e,f+1,g-1)+(1-p)*func(a,b,c,d,e+1,f+1,g+1))
return dp[a][b][c][d][e][f][g]
if f == 10: # 세 번째 돌만 기회 다 씀(도 고려해야함.)
p = 0.25 + 0.1*g
if p == 0.25:
dp[a][b][c][d][e][f][g] = max(p*func(a,b+1,c,d,e,f,g)+(1-p)*func(a+1,b+1,c,d,e,f,g+1),
p*func(a,b,c,d+1,e,f,g)+(1-p)*func(a,b,c+1,d+1,e,f,g+1))
return dp[a][b][c][d][e][f][g]
elif p == 0.75:
dp[a][b][c][d][e][f][g] = max(p*func(a,b+1,c,d,e,f,g-1)+(1-p)*func(a+1,b+1,c,d,e,f,g),
p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g))
return dp[a][b][c][d][e][f][g]
else:
dp[a][b][c][d][e][f][g] = max(p*func(a,b+1,c,d,e,f,g-1)+(1-p)*func(a+1,b+1,c,d,e,f,g+1),
p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g+1))
return dp[a][b][c][d][e][f][g]
p = 0.25 + 0.1*g
if p == 0.25:
dp[a][b][c][d][e][f][g] = max(p*func(a, b+1, c, d, e, f, g)+(1-p)*func(a+1, b+1, c, d, e, f, g+1),
p*func(a,b,c,d+1,e,f,g)+(1-p)*func(a,b,c+1,d+1,e,f,g+1),
p*func(a,b,c,d,e,f+1,g)+(1-p)*func(a,b,c,d,e+1,f+1,g+1))
return dp[a][b][c][d][e][f][g]
elif p == 0.75:
dp[a][b][c][d][e][f][g] = max(p*func(a, b+1, c, d, e, f, g-1)+(1-p)*func(a+1, b+1, c, d, e, f, g),
p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g),
p*func(a,b,c,d,e,f+1,g-1)+(1-p)*func(a,b,c,d,e+1,f+1,g))
return dp[a][b][c][d][e][f][g]
else:
dp[a][b][c][d][e][f][g] = max(p*func(a, b+1, c, d, e, f, g-1)+(1-p)*func(a+1, b+1, c, d, e, f, g+1),
p*func(a,b,c,d+1,e,f,g-1)+(1-p)*func(a,b,c+1,d+1,e,f,g+1),
p*func(a,b,c,d,e,f+1,g-1)+(1-p)*func(a,b,c,d,e+1,f+1,g+1))
return dp[a][b][c][d][e][f][g]
print(round(func(0,0,0,0,0,0,5)*100,3),"%")코드 길이가 쓸데없이 긴데, g의 범위를 판별하느라 if문을 사용해서 그렇다. g의 범위를 판별하는걸 함수 등으로 마들어서 넣었으면 코드가 훨씬 짧아졌을 듯하다. 그리고, https://myar.tistory.com/26 사이트와 확률값이 동일하게 나오는 걸로 봤을 때, 잘 구현한 듯하다.
그리고 범위 변경(성공 횟수>=14 등), 최적 선택 안내, 실시간으로 피드백을 받기 등..의 기능도 구현할 수 있겠으나, 내 목표는 일상생활에 DP 활용해보는 거였기 때문에 이 정도로 마친다.
'PS > DP' 카테고리의 다른 글
| 백준 11054번: 가장 긴 바이토닉 부분 수열 (Python) TODO (0) | 2021.10.05 |
|---|---|
| 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) TODO (0) | 2021.10.05 |
| 백준 2156번: 포도주 시식 (Python) (0) | 2021.10.02 |
| 백준 10844번: 쉬운 계단 수 (Python) TODO (0) | 2021.10.02 |
| 백준 1463번: 1로 만들기 (Python) (0) | 2021.10.02 |