[코드트리] 숫자 전

TikaToka

Dec 25, 20242y ago

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

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

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)

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

그래서

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])

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

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

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

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

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

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

Solution

# 각 플레이어의 카드 정보를 입력받습니다.
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

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])

Subscribe to 'All about TIKA'

AI Tech Blog with Curriculum Vitae

Open channel