문제 링크

시도 방법

1. 백트래킹

problems 수가 최대 6개니까 하나하나 풀다보면 백트래킹으로 가능하지 않을까 생각했다.

1. 앞으로 채워야할 능력의 수치 합을 MAX_TIME으로 지정했다.
2. 백트래킹으로 다음과 같은 3가지 케이스를 실행한다.
   1. 문제 풀 수 있으면 풀어본다. 반복문으로 풀 수 있는 문제는 다 try
   2. 그냥 능력 올리기(알고력, 코딩력 각각)

시간 초과

수치를 올릴때마다 최대 8개의 경우의 수로 갈라진다.

모든 문제를 풀 수 있을 때까지 수치를 올리려면 가장 높은 요구량을 채울 때까지 반복해야한다.

그 요구량이 R이라 치면 아마도 O(8^R) ⇒ 당연히 시간 초과

느낀 점

백트래킹을 고려할 때는 몇 개의 분기가 만들어지고 최대 몇 번 실행되는지를 생각해야겠다고 느꼈다.

2. DP

적용한 이유

1. 최소 시간 ⇒ 최적화 문제
2. 중복 최소화 ⇒ 문제를 풀든 그냥 수치를 올리든 하다보면 다른 경우로 진행했을 때와 같은 수치 상태가 될 때가 있다. ⇒ 중복 발생 ⇒ 메모이제이션으로 최소화해보자라는 생각
3. 두 개의 수치 ⇒ 2차원 배열로 해보자.

Flow

1. 최대 요구 알고력, 코딩력을 구한다.
2. 그것에 대해 DP 배열을 초기화한다.
3. (alp, cop)부터 시작하고 점수를 계산할 때 최대 요구량보다 커지면 최대 요구량으로 설정해버린다. ⇒ IndexError 방지

어려웠던 점

1. DP는 최대 요구 알고력, 코딩력까지의 범위를 가지는데 그것보다 큰 수치가 될때 IndexError를 어떻게 처리할지 고민했다. ⇒ 위의 방식대로 해결
2. 초기 alp, cop가 최대 요구량보다 이미 큰 경우에 대해 생각하지 않아 에러가 발생했다. 에러가 발생하는 이유는 alp, cop 둘 중 하나가 이미 최대 요구량보다 높으면 DP 배열이 초기화되지 않기 때문이다. 이런 경우에 대해 어떻게 처음부터 생각해낼 수 있을지 모르겠다..

코드

def solution(alp, cop, problems):
    MAX_ALP = max(map(lambda x: x[0], problems))
    MAX_COP = max(map(lambda x: x[1], problems))
    alp = min(alp, MAX_ALP)
    cop = min(cop, MAX_COP)
    dp = [[max(0, a - alp) + max(0, c - cop) for c in range(MAX_COP + 1)] for a in range(MAX_ALP + 1)]
    for a in range(alp, MAX_ALP + 1):
        for c in range(cop, MAX_COP + 1):
            for problem in problems:
                if a >= problem[0] and c >= problem[1]:
                    a_next, c_next = min(MAX_ALP, a + problem[2]), min(MAX_COP, c + problem[3])
                    dp[a_next][c_next] = min(dp[a_next][c_next], dp[a][c] + problem[4])
    return dp[MAX_ALP][MAX_COP]