백준 1315: RPG

준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.

게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.

모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.

준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.

- 입력
    - 첫째 줄에 퀘스트의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 STR[i], INT[i], PNT[i]가 주어진다. 이 숫자는 모두 1,000보다 작거나 같은 자연수이다.



- 출력
    - 첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.




예제 입력 1
5
1 1 2
3 1 1
1 3 1
10 20 5
3 3 1

예제 출력 1
4



N = int(input())
srts = [] # SRT
ints = [] # INT
pnts = [] # PNT

for _ in range(N):
    temp = list(map(int, input().split()))
    srts.append(temp[0])
    ints.append(temp[1])
    pnts.append(temp[2])

stat = [1,1] # 각각 처음의 str, int
point = 0
not_clears = []

# 1.stat 올리기 전에 깰 수 있는 quest 먼저 깨기
for i in range(N):
    if srts[i]<=stat[0] or ints[i]<=stat[1]: point += pnts[i]  # quest clear
    else: not_clears.append(i)

count = N-len(not_clears)

# 2. stat 올려서 깰 수 있는 quest 파악 하기
updates = []
for i in not_clears:
    if abs(srts[i]-stat[0])<=point or abs(ints[i]-stat[1])<=point: updates.append(i) # 얻을 수 있는 index 저장

# 3. stat 올려서 quest 깨기 - 최대 point가 되도록 DP 이용하기
if updates:

    dp = [[0,0,0] for _ in range(N)] #필요한 point, 얻게될 point
    for i in updates:
        dp[i][0] = abs(srts[i]-stat[0])    
        dp[i][1] = abs(ints[i]-stat[1])
        dp[i][2] = pnts[i]
        # point를 이용해 stat 업데이트 시키기 - 포인트 얻기
        if dp[i][0]>=dp[i][1] and dp[i][0]<=point:
            stat[0]+=dp[i][1]
            point -=dp[i][1]
            count +=1
        elif dp[i][0]<dp[i][1] and dp[i][1]<=point:
            stat[0]+=dp[i][1]
            point -=dp[i][1]
            count+=1

print(count)

겨우겨우 이렇게 풀었는뎈ㅋㅋㅋㅋㅋㅋ 역시나 틀려버렸고!!

이건 DP가 아닌 것 같은 느낌인데 어떻게 해야 DP가 쓰이는지 진짜 모르겠어,,,


python으로 된 정답 코드는 거의 없고, c++로 푼 풀이들만 있어서 이를 참고했다.

def cal(a,b):
    # 이번에 계산했던 값일때 종료
    if (dp[a][b] != -1): return dp[a][b]

    point = 0
    dp[a][b] = 0
    check = []
    for i in range(N):
        if q[i][0] <=a or q[i][1] <=b:
            dp[a][b] +=1
            if visited[i]: continue # 이전에 진행했던 quest이면 pass
            point += q[i][2]
            visited[i] = 1
            check.append(i)
    for i in range(point+1):
        dp[a][b] = max(dp[a][b], cal(min(1000, a+i), min(1000, b+(point-i)))) # 능력치는 1000이하여야 함
    # a,b 일때 했던 quest 다시 원상복귀 (이전 상태에서 다른 능력치일때를 봐야 함 )
    for i in range(len(check)): visited[check[i]] = 0
    return dp[a][b]

N = int(input())
q = [[0,0,0] for _ in range(N)] # quest 저장

for i in range(N):
    temp = list(map(int, input().split()))
    q[i][0] = temp[0]  # SRT
    q[i][1] = temp[1] # INT
    q[i][2] = temp[2] # PNT

dp = [[-1 for i in range(1001)] for j in range(1001)]
visited = [0 for i in range(1001)]
print(cal(1,1))

이번에도 역시나 피해갈 수 없는 시간초과 ㅠㅠ

c++이 연산이 가볍고 빠른건 어쩔 수 없나보닿ㅎㅎㅎㅎ


내 코드랑 비교했을 때 다른 점을 추려보면

  1. 1001 x 1001의 matrix를 만들어서 dp 정보 저장
  • 능력치가 각각 i, j 일때 최대 quest 수행 개수 dp[i][j]
  1. 재귀를 이용해 수행해야 했기에 visited 만들어서 정보 저장

크게 이 정도가 있다! 꽤 어려웠던 문제였던 건 맞는데,,,

DP 많이 복습해야지,,,, ㅜㅜ