사실 카카오 인턴 코딩테스트를 봤었기 때문에 문제의 내용과 어떻게 풀어야 할지는 대충 감을 잡은 상태로 문제를 풀었습니다.
단순히 DP로만 풀면 되겠지 하고 문제를 풀어나갔을 때 정확성만 맞고 효율성에서 시간초과가 가는 코드를 작성하였습니다.
제가 이와같은 문제를 해결할 때 두 가지 문제 점이 있었는데,
한가지는 시간복잡도 , 다른 한가지는 alp, cop 가 m_alp, m_cop ( 알고력 중 제일 높은 알고력, 코딩력 중 제일 높은 코딩력 ) 보다 큰 경우입니다.
시간 복잡도를 맞추기 위해 커팅이 필요했는데 카카오 문제풀이 해설에서 시간 복잡도가 O(목표 알고력 * 목표 코딩력 * ( problems 배열의 길이 )) 라고 하여 이에 맞게 조정하였습니다.
alp, cop 가 m_alp, m_cop 보다 큰 경우 더 이상 배울 것이 없다고 판단하여 m_alp = alp , m_cop = cop 로 조정하였습니다.
이와 같은 문제를 해결하여 효율성을 통과할 수 있었습니다.
만약 이 문제를 실제 코딩테스트에서 풀었다면 "DP로 풀어야 한다 ! " 는 알고 있어도
위의 두 가지 경우를 파악하지 못해 효율성을 통과하지 못했을 것 같습니다.
단순히 DP 문제가 아니라 DP + 커팅으로 접근했어햐 풀 수 있는 문제였습니다.
카카오에서 커팅을 좋아해서 DFS 나 BFS에서 주로 사용하는 것으로 알고있었으나 DP에서도 사용하여 놀랐습니다.
def solution(alp, cop, problems):
arr=[[1000 for _ in range(500)] for _ in range(500)]
arr[alp][cop]=0
m_alp, m_cop = max(problems,key=lambda item:item[0])[0],max(problems,key=lambda item:item[1])[1]
m_alp, m_cop = max(m_alp,alp) , max(m_cop,cop)
for x in range(alp,m_alp+1):
for y in range(cop,m_cop+1):
arr[x+1][y]=min(arr[x][y]+1,arr[x+1][y])
arr[x][y+1]=min(arr[x][y]+1,arr[x][y+1])
for problem in problems:
alp_req, cop_req , alp_rwd, cop_rwd, cost = problem[0],problem[1],problem[2],problem[3],problem[4]
if x >= alp_req and y >= cop_req:
arr[min(m_alp,x+alp_rwd)][min(m_cop,y+cop_rwd)]=min(arr[x][y]+cost,arr[min(m_alp,x+alp_rwd)][min(m_cop,y+cop_rwd)])
return arr[m_alp][m_cop]
'문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP 주사위 고르기 (0) | 2024.03.20 |
---|---|
[프로그래머스 문제풀이]2023 KAKAO BLIND RECRUITMENT 표현 가능한 이진트리 (0) | 2023.02.28 |
[프로그래머스 문제풀이] 두 큐 합 같게 만들기 (0) | 2022.08.23 |
[프로그래머스 문제풀이] 성격 유형 검사하기 문제풀이 (0) | 2022.08.23 |
[프로그래머스 문제풀이] 양과늑대 문제풀이 (0) | 2022.08.16 |