[ 카카오 / Python ] 2022 KAKAO TECH INTERNSHIP - 코딩 테스트 공부

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

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

풀이

이 문제는 DP 로 풀어야 한다.

이 문제 역시 처음에 방법은 떠올렸으나, 실제로 구현하지 못했다.

해당 해설을 참고하여 문제를 풀었다.

우리가 알고력과 코딩력을 키울 수 있는 방법은 총 3가지다.
1시간을 들여 알고력, 코딩력을 각각 늘리거나, 문제를 풀어서 문제의 보상으로 알고력, 코딩력을 늘리거나 이다.

문제가 바라는 것은 problems의 모든 문제를 풀 수 있을 때까지의 최소 시간을 구하는 것이므로..

problems 가 요구하는 최대 알고력과 최대 코딩력을 찾는다.

최대값을 바탕으로 DP 테이블을 생성한다.
초기값은 무한대로 설정하여, 최소 시간을 구할 수 있도록 한다.

처음으로 시작하는 알고력과 코딩력을 제공 해주기 때문에, 시작지점은 0으로 초기화 한다.

max_alp 까지, max_cop 까지 for-loop을 돌면서 최소 시간을 갱신한다.

# 알고력을 1 높이는 최소 시간, 현재값에 시간을 1 더하기 or 그대로 유지하기 
DP[alp + 1][cop] = min(DP[alp + 1][cop], DP[alp][cop] + 1)

# 코딩력을 1 높이는 최소 시간, 현재값에 시간을 1 더하기 or 그대로 유지하기 
DP[alp][cop + 1] = min(DP[alp][cop + 1], DP[alp][cop] + 1)

알고력과 코딩력을 단순히 1씩 증가시키는 방법은 위와 같다.

만약 풀 수 있는 문제들이 있다면

#problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
DP[alp + alp_rwd][cop_rwd] = min(DP[alp + alp_rwd][cop_rwd], DP[alp][cop] + cost)

이 문제에서 주의할 점은 인덱스 에러가 발생하지 않도록 경계값을 잘 설정해 주어야 한다.

첫번째로, 주어지는 알고력과 코딩력이 문제가 요구하는 알고력과 코딩력보다 높은 경우가 존재할 수 있다. → 이런 경우는 공부할 시간이 필요하지 않으므로 0을 리턴.

두번째로, 공부해서 얻는 알고력과 코딩력이 최대 알고력과 최대 코딩력보다 넘어갈 수 있다. → 이런 경우 DP 테이블의 범위에서 벗어나 인덱스 에러가 발생함.

그렇기 때문에 각각의 바운더리를 잘 설정해주어야 정확성 테스트 케이스에서 통과할 수 있다.

코드

def solution(alp, cop, problems):
    answer = 0
    max_alp = max_cop = 0

    for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
        max_alp = max(max_alp, alp_req)
        max_cop = max(max_cop, cop_req)

    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    times = [[float('inf') for _ in range(max_cop + 1)] for _ in range(max_alp + 1)]

    times[alp][cop] = 0

    for a in range(alp, max_alp + 1):
        for c in range(cop, max_cop + 1):
            if a + 1 <= max_alp:
                times[a + 1][c] = min(times[a + 1][c], times[a][c] + 1)
            if c + 1 <= max_cop:
                times[a][c + 1] = min(times[a][c + 1], times[a][c] + 1)

            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if a >= alp_req and c >= cop_req:
                    na, nc = min(a + alp_rwd, max_alp), min(c + cop_rwd, max_cop)
                    times[na][nc] = min(times[na][nc],
                                        times[a][c] + cost)

    answer = times[max_alp][max_cop]
    return answer