# [코드트리] 숫자 전

[코드트리 | 코딩테스트 준비를 위한 알고리즘 정석](https://www.codetree.ai/missions/2/problems/number-war?&utm_source=clipboard&utm_medium=text)

처음에는 i, j를 i번째 숫자를 사용하고 j번째 숫자를 사용할 때의 2번째 유저의 점수를 나타낸다고 하고 풀었다.

```javascript
n = int(input())

a = [0]
a += list(map(int, input().split()))
b = [0]
b += list(map(int, input().split()))

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

for i in range(1, n+1):
    for j in range(1, n+1):
        if a[i] <= b[j]:
            # if dp[i-1][j-1] != 0:
            dp[i][j] = max(dp[i-1][j-1], dp[i][j])
            # if dp[i-1][j] != 0:
            dp[i][j] = max(dp[i-1][j], dp[i][j])
        else:
            # if dp[i][j-1] != 0:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + b[j])
        
answer = 0

for i in range(1, n+1):
    answer = max(answer, max(dp[i]))

print(answer)
```

그러나 이렇게 풀 경우 마지막 테케를 통과하지 못한다.

그래서 

```javascript
n = int(input())

a = [0]
a += list(map(int, input().split()))
b = [0]
b += list(map(int, input().split()))

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

for i in range(1, n+1):
    for j in range(1, n+1):
        if a[i] <= b[j]:
            # if dp[i-1][j-1] != 0:
            dp[i][j] = max(dp[i-1][j-1], dp[i][j])
            # if dp[i-1][j] != 0:
            dp[i][j] = max(dp[i-1][j], dp[i][j])
        else:
            # if dp[i][j-1] != 0:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + b[j])
        
print(dp[n][n])
```

이렇게 푸는 경우 전부 맞다고 나온다. 하지만 뭔가 이상하다.

그래서 결국 해설을 보았는데, 

1. 비스하게 하지만 카드대결 / 버리기 의 경우로 나눠서 각각에 대회 최댓값을 구해야 한다

2. 2. 카드를 다 쓴 놈들(i==n or j==n) 들에 대해서 최댓값을 계산한다.

따라서 0 1 은 A는 카드 하나도 안버리고 B가 카드 하나 버린 상태인 

3. i, j 에서 다음으로 넘어간다고 생각해야 한다.

Solution

```javascript
# 각 플레이어의 카드 정보를 입력받습니다.
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

# dp 배열을 초기화합니다. 초기값은 -1로 설정합니다.
dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]

# 기본 케이스를 설정합니다.
dp[0][0] = 0

# 각 경우의 수를 동적 프로그래밍으로 계산합니다.
# dp[i][j] :: 첫 번째 플레이어는 i번 카드까지, 두 번째 플레이어는 j번 카드까지 버렸을 때 나올 수 있는 최대 점수
for i in range(n):
    for j in range(n):
        if dp[i][j] == -1:
            continue

        # 카드 대결 - 첫 번째 플레이어의 카드가 더 작은 경우
        if a[i + 1] < b[j + 1]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

        # 카드 대결 - 두 번째 플레이어의 카드가 더 작은 경우
        if a[i + 1] > b[j + 1]:
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j + 1])

        # 카드 버리기
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])

# 결과를 계산하여 출력합니다.
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i][n])
    ans = max(ans, dp[n][i])

print(ans)
```

챗지피티 말로는 카드가 남은 장수를 i, j로 두고 풀 수 있다고 한다

다만 마지막 dp[0][0]이 이해가 안되어서 위에 코드로 이해하였다.

code

```javascript
n = int(input().strip())

# a, b를 1~n 인덱스로 쓰기 위해 앞에 dummy 0 하나씩
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

# dp[i][j] = 플레이어1이 i장 소모, 플레이어2(남우)가 j장 소모한 상태에서
# 남우가 앞으로 얻을 수 있는 최대 점수
dp = [[0]*(n+1) for _ in range(n+1)]

# 뒤에서부터 채움: i, j를 n부터 0까지 내려오면서 계산
# (i, j) 상태에서 다음 카드가 a[i+1], b[j+1]라고 생각
for i in range(n, -1, -1):
    for j in range(n, -1, -1):
        # 이미 한쪽이 n장을 소모(즉 카드가 0장 남음)한 상태면 dp[i][j] = 0
        # => 코드상 초기값이 0이므로 그냥 넘어감
        if i == n or j == n:
            dp[i][j] = 0
            continue

        # 1) 둘 다 버리기(discard)
        discard = dp[i+1][j+1]

        # 2) 카드 대결(battle)
        if a[i+1] < b[j+1]:
            # 상대 카드(a[i+1])만 소모
            battle = dp[i+1][j]
        elif a[i+1] > b[j+1]:
            # 남우 카드(b[j+1])만 소모 + 남우 점수 증가
            battle = dp[i][j+1] + b[j+1]
        else:  # a[i+1] == b[j+1] (동점 -> 둘 다 버림, 점수 없음)
            battle = dp[i+1][j+1]

        dp[i][j] = max(discard, battle)

# 게임 시작 시점은 (0, 0) 상태
print(dp[0][0])

```

For the site tree, see the [root Markdown](https://slashpage.com/all-about-tika.md).