[python] 백준 1315 RPG

https://www.acmicpc.net/problem/1315

1315번: RPG

 

문제 해결

• 수가 크다는 것에서 우선 다이나믹 프로그래밍(DP)를 생각해 볼 수 있다. (BFS,DFS는 비현실적)
• 주어진 퀘스트를 수행할 수 있고 수행하였을 때 추가 능력치를 얻는데 이를 어디에 얼만큼 쓸 것인지 그리디 방식으로 알 수 없다. 그렇다고 브루트 포스 방식도 조금 부담스럽다.
• 그래서 3가지 리스트를 만들어 문제를 해결하는 방법을 생각할 수 있다.
  • DP[i][j]: STR=i, INT=j일 수 있는지 유무 (0,1)
  • solved[i][j]: STR=i, INT=j일 때 풀 수 있는 문제 수
  • LEFT[i][j]: STR=i, INT=j일 때 올릴 수 있는 포인트
• 그럼 DP를 어떻게 이용할 것인지 고민이 될 것이다.
• 우선 주어진 퀘스트들을 고려하여 만약 내가 STR=s, INT=i일 때 풀 수 있는 문제수 solved[s][i]를 계산 할 수 있다.
• 추가적으로 올릴 수 있는 포인트도 solved[s][i]를 계산하면서 계산할 수 있다. LEFT[s][i] = s,i일 때 풀 수 있는 퀘스트들을 풀어 얻은 포인트 - (s-i) - (i-1)
• 만약 옆에 좌표 (s-1,i)나 (s,i-1) 좌표에 올 수 있고 올릴 수 있는 포인트 (LEFT[s-1][i] or LEFT[s][i-1])가 1이상이면 (s,i)도 가능하다. 즉 DP[s][i]= 1
• 이들을 고려하여 코드 작성

CODE

import sys
input = sys.stdin.readline


def main():
    for s in range(1,1001):
        for i in range(1,1001):
            point_sum = 0
            for j in range(n):
                if quest[j][0] <=s or quest[j][1] <=i:
                    point_sum += quest[j][2]
                    solved[s][i] += 1
            LEFT[s][i] = point_sum - (s-1) - (i-1)

            if s==1 and i==1:
                DP[s][i] = 1
                continue

            if DP[s-1][i] and LEFT[s-1][i] > 0 and s-1>0:
                DP[s][i] = 1
                continue
            if DP[s][i-1] and LEFT[s][i-1] > 0 and i-1>0:
                DP[s][i] = 1
                continue

    answer = 0
    for s in range(1,1001):
        for i in range(1,1001):
            if DP[s][i]:
                answer = max(answer, solved[s][i])
    print(answer)

    return

if __name__ == "__main__":
    n = int(input())

    DP = [[0 for _ in range(1001)] for _ in range(1001)]
    LEFT = [[0 for _ in range(1001)] for _ in range(1001)]
    solved = [[0 for _ in range(1001)] for _ in range(1001)]
    quest = []
    for _ in range(n):
        X = list(map(int, input().split()))
        quest.append(X)
    main()