23.04.14 파이썬 코딩 퀴즈#218 코딩 테스트 공부(프로그래머스 스쿨)

이번 문제는 코딩 테스트 공부 문제이다.

코딩 테스트 문제를 풀기 위해서는 두가지ㅇ가 필요하다, 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현한다. (정수)

문제를 풀기 위해서는 일정 이상의 알고력 과 코딩력이 필요하다.(AND 조건)

알고력과 코딩력을 높이기 위한 방법은 3가지이다.

1. 알고력 1을 높이려면 1시간의 공부가 필요하다.

2. 코딩력 1을 높이려면 1시간의 공부가 필요하다.

3. 현재 풀 수 있는 문제를 풀게되면 해당 문제의 알고력, 코딩력 상승 점수 만큼 올릴 수 있다.

그리고 3번 방법은 문제를 풀 때마다 정해진 시간이 있으며, 여러번 풀 수 있다.

 

초기에 알고력과 코딩력을 담은 정수 alp 과 cop, 문제의 정보를 담은 2차원 정수 배열 problems 를 기준으로 모든 문제를 풀 수 있는 알고력과 코딩력으 ㄹ얻는 최단시간을 return 하는 코드를 작성해야 한다.

제한사항에서 확인해야 할 사항은 바로 problems 의 원소배열이다.

순서대로 [필요한 알고력, 필요한 코딩력, 풀었을때 증가하는 알고력, 풀었을 때 증가하는 코딩력, 푸는데 걸리는 시간]을 의미한다.

한가지 살펴볼 것은 입출력 예 2번 이다.

초기의 알고력과 코딩력은 0,0 이다. 하지만 1번 문제는 풀 수 있기 때문에 1번 문제를 2번 풀어 알고력 4, 코딩력2가 된다 (시간 4, 총 시간 4)

그 다음 코딩력만 3번 느리면 알고력 4, 코딩력 5가 된다. (시간 3. 총 시간 7)

이제 2번 문제를 풀 수 있고, 해당 문제를 2번 풀면 알고력 10, 코딩력 7이 된다 (시간 4, 총 시간 11)

이제 4번 문제도 풀 수 있다. 해당 문제를 1번 풀고 나면 알고력 10, 코딩력 11 이 된다(시간 2, 총 시간 13)

여기서 중요한 점은 3번 문제를 풀 수 있는 시점에서 모든 문제를 풀 수 있는 코딩력과 알고력을 가지게 된다는 점이다.

즉, 굳이 3번 문제를 풀 필요가 없다는 뜻이다.

반대로 얘기하면 처음 전달받은 알고력과 코딩력이 모든 문제를 풀 수 있는 수치라면, 문제의 해답은 0 이 된다.

코드는 크게 어려운 부분은 없고, dp 를 활용하여 풀었다.

먼저 problems 를 탐색하여 해당 문제에서 요구하는 최대 알고력과 코딩력을 확인하여 주었다.

문제에서 현재 알고력과 코딩력이 이 최대 수치를 초과해서 주어지는 경우가 존재하기 때문에 min()을 이용하여 현재 알고력 코딩력을 갱신해 주어야 한다.

dp 는 math.inf 로 가득채워진 2차원 배열이다.

여기서 dp[i][j] 의 값은 알고력 i, 코딩력 j 에 도달하는데 걸리는 시간을 의미하게 된다.

그리고 dp[alp][cop] = 0 으로 고정시켜 두면 된다.

조건문을 통해 i값과 j 값이 최대 index를 넘어가지 않게끔 조정해 주어야 한다.

그러면 이제 공부를 통해 알고력i, 코딩력j 에 도달하는 시간이 구해진다.

그 다음은 풀이 가능한 문제를 선택하여 풀어야 한다.

이 때에는 현재 풀이가 가능한 문제를 모두 개별적으로 풀어서 보상으로 받은 알고력/코딩력 과 현재 알고력/코딩력의 합과 최대로 필요한 알고력/코딩력을 비교하여 더 낮은 값을 선택해야 한다. 이 역시 index error를 방지하기 위함이다.

그렇게 얻은 알고력/코딩력을 좌표로 사용하여, 얻은 알고력/코딩력 좌표값과 현재 (i,j) + 걸리는 시간 을 비교하여 더 작은 값을 저장하면 된다. 즉 어느것이 최소 시간인지 판단해야 한다.

처음에는 math.inf 로 가득 채워져 있기에 바로바로 값들이 갱신되지만, 어느 시점에서는 정확히 최소값들만으로 채워진 dp가 존재하게 된다.

여기서 문제에서 요구하는 것은 problems를 모두 풀기 위한 알고력과 코딩력 이기에 dp[-1][-1] 배열의 제일 끝값을 return 해 주면 된다.