🐢 코딩 테스트 공부

1. 문제 링크

코딩 테스트 공부

2. 코드

"""
코딩 테스트 공부

💛 문제
당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다.
코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다.
알고력과 코딩력은 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

효율성 테스트 케이스 제한사항
    주어진 조건 외 추가 제한사항 없습니다.

💚 입출력
alp	cop	problems	                                        result
10	10	[[10,15,2,1,2],[20,20,3,3,4]]	                    15
0	0	[[0,0,2,1,2],[4,5,3,1,2],[4,11,4,0,2],[10,4,0,4,2]]	13

# 참고 : https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/
"""


# 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems
def solution(alp, cop, problems):
    # problems (필요한 알고력, 필요한 코딩력, 풀면 증가하는 알고력, 풀면 증가하는 코딩력, 문제 푸는데 드는 시간)
    max_alp = 0
    max_cop = 0

    for i in problems:
        # 문제들 중에 가장 높은 필요한 알고력, 코딩력
        max_alp = max(max_alp, i[0])
        max_cop = max(max_cop, i[1])

    # 현재 실력 쌓아야할 알고력, 코딩력 (근데 어차피 가장 최소 아닌지? 예외가 있나봄)
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)

    # dp[i][j] : (알고력 i, 코딩력 j) 상태에 도달하는 데 필요한 최단 시간
    # 나머지 DP 배열의 값은 무한(적당히 큰 값)으로 초기화한 후 다음과 같은 방법으로 DP 배열을 업데이트
    # dp = [[], [], [] .... , [], []]
    dp = [[1e9] * (max_cop + 1) for _ in range(max_alp + 1)]

    # 현재 도달하는 최단 시간
    # dp[초기 알고력][초기 코딩력] = 0
    dp[alp][cop] = 0

    # 궁금.. 시작값 dp[alp][cop] 이전 것들은 .. 불필요...함
    for i in range(alp, max_alp + 1) :
        for j in range(cop, max_cop + 1) :
            # 알고력 낮다면 => 공부하면 1시간 증가
            if i < max_alp :
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            # 코딩력 낮다면 => 공부하면 1시간 증가
            if j < max_cop :
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)

            # 문제 풀기 (수준에 맞지 않는다면 그만큼 공부하기)
            # problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems :
                # 알고력, 코딩력이 수준에 맞다면
                if i >= alp_req and j >= cop_req :

                    # 문제 푼거에 대한 증가하는 알고력, 코딩력
                    nalp = min(i + alp_rwd, max_alp)
                    ncop = min(j + cop_rwd, max_cop)
                    # 문제 푸는 시간 (같거나, 작거나)
                    dp[nalp][ncop] = min(dp[nalp][ncop], dp[i][j] + cost)
    # alp_req, cop_req 가 해당하면 그만큼 문제 여러번 풀 수 있음
    # 그러다가 그다음 수준에 해당하면 넘어가고, 각각에 대한 알고력, 코딩력 공부하기 (그러면 그 전 문제 못 품)
    # 2 1
    # 4 2

    # 4 5
    # 7 6
    # 10 7
    # 10 11
    # 그 전에 못 푼애들은 최대에 의해 이미 푼걸로 간주
    return dp[max_alp][max_cop]

• 정확성

    정확성  테스트
    테스트 1 〉	통과 (0.19ms, 10.3MB)
    테스트 2 〉	통과 (0.23ms, 10.2MB)
    테스트 3 〉	통과 (0.08ms, 10.3MB)
    테스트 4 〉	통과 (0.03ms, 10.4MB)
    테스트 5 〉	통과 (0.15ms, 10.4MB)
    테스트 6 〉	통과 (0.19ms, 10.3MB)
    테스트 7 〉	통과 (0.04ms, 10.3MB)
    테스트 8 〉	통과 (0.03ms, 10.2MB)
    테스트 9 〉	통과 (0.07ms, 10.4MB)
    테스트 10 〉	통과 (0.04ms, 10.3MB)
    효율성  테스트
    테스트 1 〉	통과 (19.69ms, 10.3MB)
    테스트 2 〉	통과 (28.54ms, 10.5MB)
    테스트 3 〉	통과 (3.65ms, 10.5MB)
    테스트 4 〉	통과 (19.72ms, 10.3MB)
    테스트 5 〉	통과 (128.26ms, 10.3MB)
    테스트 6 〉	통과 (34.20ms, 10.5MB)
    테스트 7 〉	통과 (174.21ms, 10.4MB)
    테스트 8 〉	통과 (139.41ms, 10.3MB)
    테스트 9 〉	통과 (323.42ms, 10.5MB)
    테스트 10 〉	통과 (4.49ms, 10.3MB)
    채점 결과
    정확성: 50.0
    효율성: 50.0
    합계: 100.0 / 100.0
  

3. 해설

• 문제 푸는 것 중에 최대 코딩력과 알고력을 기준을 잡음
  • 최대로 필요한 코딩력, 알고력 보다 큰 것을 가질 필요가 없음 (최대 시간이니까 더 크면 안됨!)
• 알고력, 코딩력 따로따로 공부력을 증가시켜야 함
  • 기준치에 맞을 때까지 for 문으로 공부시킨다
  • 최대치에 도달할 때까지

• 문제가 순서대로가 아니어도, 최대에 기준에 의해 푼 걸로 간주해서 안올라감.

  • ex) 2번 맞나?

  # 그러다가 그다음 수준에 해당하면 넘어가고, 각각에 대한 알고력, 코딩력 공부하기 (그러면 그 전 문제 못 품)
      # 2 1
      # 4 2
  
      # 4 5
      # 7 6
      # 10 7
      # 10 11
      # 그 전에 못 푼애들은 최대에 의해 이미 푼걸로 간주