PROGRAMMERS 코딩 테스트 공부

https://school.programmers.co.kr/learn/courses/30/lessons/118668

input :

• 0 ≤ alp, cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소 : [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태

output :

• 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return

조건 :

• 알고력 1을 높이기 위해서 1의 시간이 필요
• 코딩력 1을 높이기 위해서 1의 시간이 필요
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

---

idea

모든 alp, cop에 대해서 시간을 구한다면?? 근데 어떻게 구현할지가 문제였음.
특정 포인트에서만 답을 구하는 것은 좋지 않음.

그리고 기본적으로 1시간을 사용해서 alp 또는 cop를 얻을 수 있는데 이를
problems에다가 넣어서 계산을 편하게 하자.

---

2022.12.30

문제점

1. 정확한 alp, cop를 찾으려 했음. 해당 문제를 풀기 위해선 그 이상이 되면 된다는 것.
2. 위의 문제로 인해 x - alp_req와 같은 형식 사용. 제한된 결과만 가져왔음.
3. alp, cop가 최대의 alp_req들 보다 큰 경우를 생각안함. (index 문제 발생)

---

해설

해설
해설에서는 i, j에서 i + alp_rwd, j + cop_rwd에 대해서의 점화식을 구현했다.

모든 i, j에 대해 하는 것이 편할 거 같아서 이렇게 했지만 문제가 존재했다.

주의

요구하는 alp, cop 보다 커지는 경우에도 특정 시간에 이 결과를 기록하는 방식이 필요함.
그래서 i, j에다가 더하는 방식이 유효함.

그리고 alp, cop = min(alp, req_alp), min(cop, req_cop) 해당 라인이 유효한 이유는?
1. 우선 req_alp 또는 req_cop 가 초기 값보다 작은 경우를 대비함.
2. dp를 계산할 때의 조건이 이를 위주로 제작됨. 그래서 dp를 구하는 연산 자체가 수행이 안 될 수도 있어서 괜찮음.

def solution(alp, cop, problems):
    req_alp, req_cop = -1, -1
    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
        req_alp = max(req_alp, alp_req)
        req_cop = max(req_cop, cop_req)

    problems.append([0, 0, 1, 0, 1])
    problems.append([0, 0, 0, 1, 1])

    dp = [[float("inf")] * (req_cop + 1) for _ in range(req_alp + 1)]
    alp, cop = min(alp, req_alp), min(cop, req_cop)
    dp[alp][cop] = 0

    for x in range(alp, req_alp + 1):
        for y in range(cop, req_cop + 1):

            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                dx, dy = min(x + alp_rwd, req_alp), min(y + cop_rwd, req_cop)
                if x < alp_req or y < cop_req:
                    continue
                dp[dx][dy] = min(dp[dx][dy], dp[x][y] + cost)

    return dp[req_alp][req_cop]