[프로그래머스 Lv3] 파이썬 - 코딩 테스트 공부

프로그래머스 - 코딩 테스트 공부

# 조건

• 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다.
• 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.
• 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다.
• 알고력과 코딩력은 0 이상의 정수로 표현됩니다.
• 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.
  • 예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.
  • A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
  • B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.
• 풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다.
• 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.
  • 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
  • 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다.
• 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.
• 당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.
• 초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.
  • 모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

---

제한사항

• 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
  • 0 ≤ alp,cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
• alp_req는 문제를 푸는데 필요한 알고력입니다.
  • 0 ≤ alp_req ≤ 150
• cop_req는 문제를 푸는데 필요한 코딩력입니다.
  • 0 ≤ cop_req ≤ 150
• alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
  • 0 ≤ alp_rwd ≤ 30
• cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
  • 0 ≤ cop_rwd ≤ 30
• cost는 문제를 푸는데 드는 시간입니다.
  • 1 ≤ cost ≤ 100

정확성 테스트 케이스 제한사항

• 0 ≤ alp,cop ≤ 20
• 1 ≤ problems의 길이 ≤ 6
  • 0 ≤ alp_req,cop_req ≤ 20
  • 0 ≤ alp_rwd,cop_rwd ≤ 5
  • 1 ≤ cost ≤ 10

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

# 접근 방법

• deque를 이용한bfs를 홀용하여 풀어줘도 되지만 효율성 테스트를 통과할 수 없다.
  • 다만 heapq를 이용하여 다익스트라와 같이 풀어줄 수는 있다.
• 따라서, dp를 활용하여 풀어주는데 점화식은 아래와 같다.
  • dp[i][j] = 알고력 i, 코딩력 j를 도달 할 수 있는 최단 시간
  • 우선 최대로 얻어야하는 max 값을 구해준다.
  • 이 때, 알고력 코딩력 중 하나라도 목표 값을 넘어가지 않도록 설정해준다.
• dp[alp][cop]를 0으로 초기화 해준 후 반복문을 돌린다.
  • 반복문의 범위는 초기 알고력부터 최대 알고력까지
  • 초기 코딩력부터 최대 코딩력까지이다.
• 우선 얻어야되는 값보다 알고력, 코딩력이 낮다면 1시간에 1씩 올릴수 있으므로 +1 씩 해준다.
• problems를 순회하며 문제로 얻는 알고력과 코딩력을 더해주는데 둘 중 하나라도 목표값을 넘어가지 않게 비교해준다.
• 이후, dp 값을 최소값으로 갱신해준다.
• dp 문제는 연습이 필요한 것 같다..

def solution(alp, cop, problems):
    # 필요한 알고력, 코딩력 구해주기
    # dp크기는 dp[-1][-1]이 필요한 알고력, 코딩력이 되도록 크기 설정
    need_alp, need_cop = max([i[0] for i in problems]), max([i[1] for i in problems])
    dp = [[float('inf')] * (need_cop +1) for _ in range(need_alp+1)]

    # 시작 알고력보다 필요 알고력이 낮을 수 잇으므로 초기화 시켜준다.
    alp, cop = min(alp, need_alp), min(cop, need_cop)
    dp[alp][cop] = 0

    # 1시간에 1씩 올릴 수 있으므로 1씩 올리며 탐색
    for i in range(alp, need_alp+1):
        for j in range(cop, need_cop+1):
            if i < need_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
            if j < need_cop:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)

            # 문제 풀이로 탐색
            # 문제를 풀 수 있는 알고력과 코딩력을 갖췄다면
            # 현재 문제로 얻게 되는 알고력 코딩력을 기록해주는데
            # 필요 이상으로 넘어가지 않도록 더해준다.
            for req_alp, req_cop, rwd_alp, rwd_cop, cost in problems:
                if i >= req_alp and j >= req_cop:
                    now_alp, now_cop = min(i + rwd_alp, need_alp), min(j+rwd_cop, need_cop)

                    dp[now_alp][now_cop] = min(dp[now_alp][now_cop], dp[i][j]+cost)

    return dp[need_alp][need_cop]