알고리즘 - Python / 백준 - 14677번 : 병약한 윤호

14677번: 병약한 윤호 (acmicpc.net)

14677번: 병약한 윤호

 

---

풀이

• 약봉투가 일렬로 있을 때 , 아침 , 점심 , 저녁 약을 순서대로 중간의 약봉투를 끊지 않고 먹을 수 있는 최대의 경우의 수를 구하는 문제다.
• 부분 문제의 답들이 모여 전체 문제의 답이 될 수 있으므로 , DP로 접근했다.
• DP 배열은 DP[왼쪽에서 뜯은 약의 개수][오른쪽에서 뜯은 약의 개수] = 그 단계의 최대 약의 개수로 두었다.
• 처음에 DP[1][0] (왼쪽에서 하나 뜯는 경우)와 DP[0][1] (오른쪽에서 하나 뜯는 경우)에서 아침 약을 먹는지 확인하고 아침 약이라면 배열 값을 1로 바꾼다.
• 이후 2차원 배열을 대각선으로 계속 훑으면서 체크하면 된다.
• 만약 , 왼쪽 혹은 오른쪽에서 모두 뜯을 수 없는 경우는 , 그대로 배열값을 두고 한쪽만 뜯을 수 있는 경우는 그 부분만 뜯어 배열 값을 이전 경우 + 1로 업데이트하였다.
• 왼쪽 혹은 오른쪽에서 모두 뜯을 수 있는 경우, DP 식은 ( 대각으로 체크해서 k와 i-k 이중 for문 ) 아래와 같다.
• DP[k][i-k] = MAX(DP[k-1][i-k] , DP[k][i-k-1])
• 예를 들어 DP[2][3]의 뜻은 왼쪽에서 2개 , 오른쪽에서 3개 뜯었다는 뜻이다.
• DP[2][3]이 될 수 있는 경우는 DP[1][3]에서 왼쪽 것을 하나 뜯는 경우와 DP[2][2]에서 오른쪽 것을 하나 뜯는 경우가 존재한다.
• 따라서 DP 점화식이 위처럼 나오게 되는 것이다.

 

import sys
n = int(sys.stdin.readline())
s = list(sys.stdin.readline().replace("\n",""))
dp = [[-501 for i in range((3*n)+1)] for k in range((3*n)+1)]
check = ["D","B","L"]
if s[0] == "B":
    dp[1][0] = 1
if s[-1] == "B":
    dp[0][1] = 1
for i in range(2,(3*n)+1):
    if s[-i] == check[i%3]:
        dp[0][i] = dp[0][i-1] + 1
    if s[i-1] == check[i%3]:
        dp[i][0] = dp[i-1][0] + 1
    for k in range(1,i):#k , i-k
        if s[k-1] == check[i%3] and s[-(i-k)] == check[i%3]:
            dp[k][i-k] = max(dp[k-1][i-k] , dp[k][i-k-1]) + 1
        elif s[k-1] == check[i%3]:
            dp[k][i-k] = dp[k-1][i-k] + 1
        elif s[-(i-k)] == check[i%3]:
            dp[k][i-k] = dp[k][i - k - 1] + 1
ans = 0
for i in dp:
    pp = max(i)
    ans = max(ans,pp)
print(ans)

---