[Programmers] level3 - 코딩 테스트 공부 (Python) : 2022 카카오 테크 인턴십

▶코딩 테스트 공부 - 2022 카카오 테크 인턴십 (level 3)

▶문제

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

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

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

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

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

728x90

▶입출력 예

입출력 예 #1

1. 코딩력 5를 늘립니다. 알고력 10, 코딩력 15가 되며 시간이 5만큼 소요됩니다.
2. 1번 문제를 5번 풉니다. 알고력 20, 코딩력 20이 되며 시간이 10만큼 소요됩니다. 15의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.

 

입출력 예 #2

1. 1번 문제를 2번 풉니다. 알고력 4, 코딩력 2가 되며 시간이 4만큼 소요됩니다.
2. 코딩력 3을 늘립니다. 알고력 4, 코딩력 5가 되며 시간이 3만큼 소요됩니다.
3. 2번 문제를 2번 풉니다. 알고력 10, 코딩력 7이 되며 시간이 4만큼 소요됩니다.
4. 4번 문제를 1번 풉니다. 알고력 10, 코딩력 11이 되며 시간이 2만큼 소요됩니다. 13의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.

 

▶풀이

problems에서 주어진 alp_req, cop_req를 이용해서 max_alp, max_cop를 구한다.

dp를 이용해서 문제를 푸는데 alp, cop이 max값을 넘어서면 indexError가 발생할 수 있기 때문이다.

 

그렇게 구한 max값으로 dp를 만들어준다. (2차원)

당연히 dp[alp][cop]은 0이 된다. (바로 해결 가능하니까.)

 

alp ~ max_alp, cop ~ max_cop으로 2중 for문을 구성한다.

i + 1과 j + 1을 기준으로 먼저 하는데, 이는 그냥 alp나 cop을 1 증가시킴으로써 도달할 수 있기 때문이다.

 

그다음에 모든 problem에 대해서 반복문을 돌리면서 비교해준다.

i, j에서 alp_rwd와 cop_rwd로 이동할 수 있는 곳을 next에 저장한다.

max값과 비교해 min으로 정하는 이유는, max이상이 된다면 그냥 max에 값을 저장하면 되기 때문이다.

당연히 next에 해당하는 dp에는 cost를 추가해서 min값을 넣어주면 된다.

 

그렇게 비교를 다하고 나면 마지막으로 dp[-1][-1]을 return 해주면 된다.

def solution(alp, cop, problems):
    max_alp, max_cop = 0, 0
    
    for i in range(len(problems)):
        max_alp = max(problems[i][0], max_alp)
        max_cop = max(problems[i][1], max_cop)
        
    alp = min(max_alp, alp)
    cop = min(max_cop, cop)
    max_cost = 100 * (max_alp + max_cop)
    dp = [[max_cost + 1 for _ in range(max_cop + 1)] for _ in range(max_alp + 1)]
    dp[alp][cop] = 0
    for i in range(alp, max_alp + 1):
        for j in range(cop, max_cop + 1):
            if i + 1 <= max_alp:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
            if j + 1 <= max_cop:
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)
            
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if i >= alp_req and j >= cop_req:
                    next_alp = min(max_alp, i + alp_rwd)
                    next_cop = min(max_cop, j + cop_rwd)
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[i][j] + cost)
        
                    
    return dp[-1][-1]

max값을 설정해주는 게 중요한 거 같다.

나도 처음에 그 부분은 생각하지 못했다.

다른 분의 힌트를 얻어서 해결했다. (그 부분이 조금 아쉽다.)

다음에는 그런 힌트 없이도 스스로 해결할 수 있도록 노력해야겠다.