문제 링크: https://www.acmicpc.net/problem/14613

Thumbnail: Photo by Fredrick Tendong (Unsplash)

DP는 배열을 어떻게 설계할 지가 항상 직관적으로 보이지 않아 어려운 것 같습니다...

풀이

DP 배열 힌트

도저히 떠오르는 게 없어서 질문 게시판을 보며 DP 배열의 힌트를 얻었습니다.

처음에는 승리/패배/무승부 횟수 3가지를 전부 DP 배열의 인덱스로 써야 하나 싶었지만, 막상 그렇게 쓰면 3 차원 배열이 되고, DP 배열을 채우는 과정도 복잡해진다고 생각했습니다.

하지만, DP 배열을 진행한 게임 수와 현재 랭크 점수의 2가지로 DP 배열을 만들면, 직관적으로 DP 배열을 채워나갈 수 있습니다. DP 배열에 채울 값은 해당 경우에 도달할 수 있는 확률입니다.

DP 배열 채우기

DP 배열은 구현의 편의를 위해 3500까지 만들어 두었지만, 실제로 점수는 50점 단위로 변화하므로 50의 배수가 아닌 구간은 전부 사용하지 않습니다. 따라서, 배열의 크기를 줄이고 점수 계산 시 50을 곱하는 것도 유용한 방법이라고 생각되나, 따로 시도해 보지는 않았습니다.

W, L, D = map(float, input().split())
DP = [[0.0 for _ in range(3501)] for _ in range(21)]
DP[0][2000] = 1.0

for i in range(1, 21):
    for j in range(0, 3501, 50):   # 어짜피 50점 단위로 변화한다.
        if DP[i - 1][j] > 0:
            # 승리
            DP[i][j + 50] += DP[i - 1][j] * W
            # 패배
            DP[i][j - 50] += DP[i - 1][j] * L
            # 무승부
            DP[i][j] += DP[i - 1][j] * D

앞서 DP 배열을 진행한 게임 수와 현재 랭크 점수로 구성했습니다. 따라서, 1부터 20까지 반복하며 점수의 변화를 DP 배열에 기록하면 됩니다.

• 승리한 경우:
  • 진행한 게임 수는 1 증가
  • 현재 랭크 점수는 50 증가
• 패배한 경우
  • 진행한 게임 수는 1 증가
  • 현재 랭크 점수는 50 감소
• 무승부인 경우
  • 진행한 게임 수는 1 증가
  • 현재 랭크 점수는 그대로

DP 배열을 모두 0으로 초기화한 후 확률을 계산하고 있으므로, 이전 번 게임의 모든 점수 구간을 탐색해 만약 해당 칸의 확률이 0 이 아니라면 다음 경우를 계산해주면 됩니다.

전체 코드

input = open(0).readline
W, L, D = map(float, input().split())

RESULTS = [0.0 for _ in range(5)]  # 브 실 골 플 다
DP = [[0.0 for _ in range(3501)] for _ in range(21)]
DP[0][2000] = 1.0

for i in range(1, 21):
    for j in range(0, 3501, 50):   # 어짜피 50점 단위로 변화한다.
        if DP[i - 1][j] > 0:
            # 승리
            DP[i][j + 50] += DP[i - 1][j] * W
            # 패배
            DP[i][j - 50] += DP[i - 1][j] * L
            # 무승부
            DP[i][j] += DP[i - 1][j] * D

for i in range(0, 3501, 50):
    if 1000 <= i < 1500:
        RESULTS[0] += DP[20][i]
    elif 1500 <= i < 2000:
        RESULTS[1] += DP[20][i]
    elif 2000 <= i < 2500:
        RESULTS[2] += DP[20][i]
    elif 2500 <= i < 3000:
        RESULTS[3] += DP[20][i]
    elif 3000 <= i < 3500:
        RESULTS[4] += DP[20][i]

for i in range(5):
    print(f"{RESULTS[i]:.8f}")