Willing

1. 문제 / 난이도 : Gold Ⅲ

www.acmicpc.net/problem/11062

2. 풀이 및 코드 설명

전형적인 DP문제. 처음에는 근우의 입장에서만 생각하고 코드를 짠 후 당당하게 제출했는데 역시 당당하게 틀렸다. 해당 문제는 다음과 같이 근우의 차례일 때와 명우의 순서일 때를 나누어서 생각해야 한다.

(1) 근우의 순서일 때

    - 왼쪽 카드를 선택하고 나머지 카드들에서 얻는 점수, 오른쪽 카드를 선택하고 나머지 카드들에서 얻는 점수 중 최댓값

(2) 명우의 순서일 때

    - 왼쪽 카드 제외한 나머지 카드들에서 얻는 점수, 오른쪽 카드 제외한 나머지 카드들에서 얻는 점수 중 최솟값

    - 근우가 점수를 작게 가져가게끔 만들어야하도록 최솟값일 때의 경우를 선택

간단한 코드이므로 코드 블락 단위의 설명은 주석으로 대체하겠음.

3. 전체 코드

def pickCard(turn, i, j):
    if i > j: return 0
    if dp[i][j]: return dp[i][j] #이미 계산된 적이 있으면 해당 값 리턴
    
    #근우 차례
    if turn:
        # i카드 + (i+1~j)범위 카드의 명우 순서 or j카드 + (i~j-1)범위 카드의 명우 순서 중 최대 스코어
        score = max(pickCard(False, i+1, j) + cards[i], pickCard(False, i, j-1) + cards[j]) 
        dp[i][j] = score
        return score
        
    #명우 차례
    elif not turn:
        # (i+1~j)범위 카드의 근우 순서 or (i~j-1)범위 카드의 근우 순서 중 최소 스코어
        # 각각 명우가 i, j 카드를 가져갔다고 가정하지만, 근우 입장의 점수를 계산하는 거기 때문에 카드 점수를 더해주지 않음
        score = min(pickCard(True, i+1, j), pickCard(True, i, j-1))
        dp[i][j] = score
        return score

import sys
T = int(input()) #테스트케이스

for _ in range(T):
    N = int(input()) #카드 개수
    cards = list(map(int, sys.stdin.readline().split()))
    dp = [[0 for _ in range(N)] for _ in range(N)] #DP 배열 초기화
    pickCard(True, 0, N-1) #카드가 (0~N-1)범위만큼 있고,  근우 순서일 때 얻는 점수 계산
    print(dp[0][N-1])

1. 문제 / 난이도 : Gold Ⅳ

www.acmicpc.net/problem/2572

2. 풀이 및 코드 설명

처음에는 가능한 모든 경우의 수를 다 해봐야 하나...? 라고 생각했지만 K의 최대가 10000이고, N의 최대가 1000이어서 모든 경우의 수를 돌면 10000의 1000제곱....빠르게 포기했다. 다른 방법을 생각해보았다.

그래서 그 다음 생각한 방법이 DP를 이용해 푸는 것! 다음과 같은 입력이 들어올 때로 예를 들면,

5
R G R B G
4 5
1 2 R
1 3 G
2 3 G
1 4 R
4 3 B

다섯번째 G 카드를 들고 있을 때 각각의 마을에서 얻는 점수를 계산해보면, DP 배열은 다음과 같다

그 다음, 네번째 B 카드를 들고 있을 때 1번 마을의 경우를 살펴보면 => 1번 마을에서는 2, 3, 4번 마을로 갈 수 있으므로

2번 마을로 가는 경우 = DP[5][2] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 0 = 10 + 0 = 10

4번 마을로 가는 경우 = DP[5][4] + 0 = 0 + 0 = 0

세가지 경우의 MAX값은 10이다.

(* 빨간색 숫자는 해당 마을로 움직일 때 얻는 점수, B카드를 들고 있을 때 1번에서 2번 마을로 가는 경우에는 R색의 길을 지나므로 점수를 얻기 때문에 0을 더해준다)

마찬가지로 네번째 B 카드를 들고 있을 때 4번 마을의 경우를 살펴보면 => 4번 마을에서는 1, 3번 마을로 갈 수 있으므로

1번 마을로 가는 경우 = DP[5][1] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 10 = 10 + 10 = 20

두가지 경우의 MAX값은 20이다.

위와 같은 과정을 거쳐 DP배열은 전부 채우면, DP는 다음과 같은 형태가 된다.

원하는 것은 1번 마을에서 첫번째 카드를 들고 있을 때 얻을 수 있는 점수의 최댓값이므로 DP[1][R]이 답이된다.

(1) 설정 및 초기화

# 보드 정보 저장
for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))
# dp 배열 초기화
dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

board[i] : i에서 갈 수 있는 정점과, 그 때 지나는 길의 색이 튜플 형태로 저장되어 있음

(2) DP배열 채우기

for i in range(N-1, -1, -1): # 카드를 하나씩 돌면서
    current_card = cards[i] # 현재 카드
    for j in range(M, 0, -1): # 각 마을을 하나씩 돌면서
        temp = 0
        for k in board[j]: # 해당 마을에서 갈 수 있는 정점의 정보
            node = k[0] # 정점 번호
            vertex = k[1] # 길의 색
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp) # 모든 경우의 최댓값
        dp[i][j] = temp

3. 전체 코드

import sys

N = int(input())
cards = sys.stdin.readline().split()
M, K = map(int, sys.stdin.readline().split())
board = [[] for _ in range(M + 1)]

for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))

dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

for i in range(N-1, -1, -1):
    current_card = cards[i]
    for j in range(M, 0, -1):
        temp = 0
        for k in board[j]:
            node = k[0]
            vertex = k[1]
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp)
        dp[i][j] = temp
print(dp[0][1])