[프로그래머스] 코딩 테스트 공부 [Level 3] (python 파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

def solution(alp, cop, 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])
    if max_alp < alp:
        alp = max_alp
    if max_cop < cop:
        cop = max_cop
    dp = [[155 for i in range(max_cop+1)] for j 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][j]+1, dp[i+1][j])
            if j+1 <= max_cop:
                dp[i][j+1] = min(dp[i][j]+1, dp[i][j+1])
           
            for problem in problems:
                alp_req = problem[0]
                cop_req = problem[1]
                alp_rwd = problem[2]
                cop_rwd = problem[3]
                cost = problem[4]
                if alp_req <= i and cop_req <= j:
                    next_alp,next_cop = min(max_alp,i + alp_rwd), 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]

 

 

 

 

이 문제를 dp를 이용하여 풀 수 있다.

 

이차원 dp를 만들어서 문제를 풀어보자. 

 

 

 

우선 모든 문제를 풀 수 있는 알고력과 코딩력을 알기 위해, for문을 통해 알아낸다. 

 

 

                                            

 

	cop
alp	0	155	155	155	155	155
	155	155	155	155	155	155
	155	155	155	155	155	155
	155	155	155	155	155	155
	155	155	155	155	155	155
	155	155	155	155	155	155
	155	155	155	155	155	155

  이런 모양의 이차원 dp를 만든다.

dp[alp][cop] == alp 와 cop를 요구하는 문제를 풀 수 있는 최소 시간

 

 

초기 입력 alp, cop 에 대해 dp[alp][cop] = 0 으로 두고 시작

나머지는 155 로 초기화 (dp를 진행하며 최소화 하기 위해 초기화 값을 가능한 최댓값으로 설정 (문제에서는 150이므로 넉넉히 155로 설정))

 

 

 

 

 

for 문을 돌면서 이차원 dp를 하나씩 돈다.

 

이때 수행할 수 있는 경우의 수는 3가지이다.

1. 알고력을 높이기 위해 알고리즘 공부를 한다.

2. 코딩력을 높이기 위해 알고리즘 공부를 한다.

3. 문제를 풀어 알고력과 코딩력을 올린다.

 

 

 

 

 

따라서 각각의 dp에 대해서 이 3가지 경우를 모두 실시하면 된다.

 

 

 

 

1번의 경우

if i+1 <= max_alp:
                dp[i+1][j] = min(dp[i][j]+1, dp[i+1][j])

 

만약 필요한 최대 알고력보다 크면 굳이 할 필요도 없으며 리스트 범위를 벗어나기 때문에 제외한다.

 

알고리즘 공부를 하면 알고력이 1 올라가며, 시간도 1 올라간다.

따라서 dp[i+1][j] = dp[i][j] +1 이다. (현재값 dp[i][j]의 시간에서 1을 더한 시간은 dp[i+1][j]의 시간이다. {알고력을 올렸기에 i가 올라간다})

이때 이미 dp[i+1][j] 의 시간이 충분히 작은 시간으로 도달 가능할 수도 있으므로 이 두 값을 비교하여 입력해야한다.

 

 

 

 

2번의 경우

if j+1 <= max_cop:
                dp[i][j+1] = min(dp[i][j]+1, dp[i][j+1])

 

만약 필요한 최대 코딩력보다 크면 굳이 할 필요도 없으며 리스트 범위를 벗어나기 때문에 제외한다.

 

코딩 공부를 하면 코딩력이 1 올라가며, 시간도 1 올라간다.

따라서 dp[i][j+1] = dp[i][j] +1 이다. (현재값 dp[i][j]의 시간에서 1을 더한 시간은 dp[i][j+1]의 시간이다 {코딩력을 올렸기에 j가 올라간다.})

이때 이미 dp[i][j] 의 시간이 충분히 작은 시간으로 도달 가능할 수도 있으므로 이 두값을 비교하여 입력해야한다

 

 

 

 

3번의 경우 

for problem in problems:
                alp_req = problem[0]
                cop_req = problem[1]
                alp_rwd = problem[2]
                cop_rwd = problem[3]
                cost = problem[4]
                if alp_req <= i and cop_req <= j:
                    next_alp,next_cop = min(max_alp,i + alp_rwd), min(max_cop,j + cop_rwd)
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop],dp[i][j] + cost)

 

 

 

1. 모든 문제를 돈다. (최대 문제 개수가 100개이므로 모두 돌아도 오랜 시간이 걸리지 않을 거라는 근거)

 

2. 인덱스로 접근하기에는 햇갈리므로 나에게 편한 이름으로 초기화했다.

 

3. 문제의 조건을 충족하는 경우에만 실시 (문제를 풀기에 필요한 코딩력과 알고력을 넘었을 경우에만)

 

 

3-2. 현재 문제를 풀었을 경우 결과값의 dp(다음 dp) 에 시간 갱신

next_alp,next_cop = min(max_alp,i + alp_rwd), min(max_cop,j + cop_rwd)

이때  현재 문제를 풀었을 경우 결과값이 최댓값보다 크면 dp의 최댓값으로 갱신 (리스트를 넘기 때문에 인덱스 에러 발생)

 

dp[next_alp][next_cop] = min(dp[next_alp][next_cop],dp[i][j] + cost)

 

 

 

 

 

 

 

정리 

1. 이 문제는 이차원 dp를 이용해야 한다. 

 

2. 위의 그림처럼 머릿속에서 이차원 표의 x축 과 y축을 cop와 alp로 생각해낼 수 있어야 한다.

 

3. 또한 dp의 범위를 주어진 문제를 모두 풀 수 있는 최소의 alp와 cop로 지정하여 최대한 dp를 작게 만들어 연산을 줄이는 방법을 이용한다. 

 

4. 답안 중에 현재 alp와 cop력에서 공부나 문제를 풀었을 때, dp의 범위 보다 큰 경우는 제외하거나 dp의 최댓값으로 갱신하였다.

이러한 방법을 통해 마지막 dp[-1][-1]에 우리가 원하는 값이 들어갈 수 있도록 유도 할 수 있으며, 최대한 연산의 횟수를 줄일 수 있다.