2023. 10. 14. 22:39ㆍ알고리즘 풀이
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.
알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 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
입출력 예 설명
입출력 예 #1
코딩력 5를 늘립니다. 알고력 10, 코딩력 15가 되며 시간이 5만큼 소요됩니다.
1번 문제를 5번 풉니다. 알고력 20, 코딩력 20이 되며 시간이 10만큼 소요됩니다. 15의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.
입출력 예 #2
1번 문제를 2번 풉니다. 알고력 4, 코딩력 2가 되며 시간이 4만큼 소요됩니다.
코딩력 3을 늘립니다. 알고력 4, 코딩력 5가 되며 시간이 3만큼 소요됩니다.
2번 문제를 2번 풉니다. 알고력 10, 코딩력 7이 되며 시간이 4만큼 소요됩니다.
4번 문제를 1번 풉니다. 알고력 10, 코딩력 11이 되며 시간이 2만큼 소요됩니다. 13의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.
제한시간 안내
정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수참고해서 푼 풀이
- 풀이를 떠올리기 어려웠다.
- 그러나 배울 점은 많은 문제다
- 첫 번째로 problems에 직접 값을 넣어줌으로써 하나를 1만큼 늘릴 때는 코스트는 무조건 1이라는 것을 단순화할 수 있다.
- 두 번째로 max_alp, max_cop가 이미 클 수가 있는데 이를 최댓값으로 제한해서 문제를 단순화하고 있다.
- 세 번째로 마찬가지로 max_alp, max_cop보다 큰 결과가 생기면 max_alp, max_cop에 값을 넣어주어서 문제를 단순화하고 있다.
- 네 번째로 dp의 제일 중요한 점은 점화식에서 우변은 항상 최소가 보장되어야 한다는 것이다.(AiBj = Ai-aBj-b + alpha) 만약 for문을 돌며 우변에 해당하는 것을 이미 계산해줬는데 그 우변의 값이 변하게 된다면(더 최소가 나타나서) 이전에 계산했던 좌변은 최소를 보장할 수가 없는 것이다. 그러니까 for문을 돌았을때 이를 보장해준다는 것이다. 사실 이게 안될 거 같아 for문 돌리는 것을 배제했었다.
- 근데 이게 되는 이유는 alp+2, cop인 친구는 alp, cop+10인 친구에게 절대 영향을 줄 수 없기 때문이다. 왜냐하면 alp + 2는 alp보다 큰데 cost에는 -가 없기 때문이다. 따라서 alp, cop +1부터 alp, cop+10까지 가는 동안 최소가 보장되는 것이다. 이러한 논리를 다음 dp 문제를 풀 때 참고하자
- 즉 dp list를 for 문으로 도는데 이전의 element가 이후 element에 의해 변할 일이 없다면 for 문을 사용해도 괜찮은 것이다.
def solution(alp, cop, problems):
# 최소를 찾아야 하므로 그리디, DP, 탐색
# 항상 최선의 선택을 할 수 없으므로 그리디 X
# 중간 결과를 이용할 수 있는 DP
# 탐색을 하기에는 경우의 수가 많아지므로 보류
# 알고력과 코딩력 각각을 가지기 위한 최소한의 시간을 담는 dp를 정의
problems.append([0,0,0,1,1])
problems.append([0,0,1,0,1])
max_alp, max_cop = 0, 0
for problem in problems:
alp_req, cop_req = problem[0], problem[1]
max_alp = max(max_alp, alp_req)
max_cop = max(max_cop, cop_req)
alp = min(alp, max_alp)
cop = min(cop, max_cop)
dp = [[float('inf')] * (1+max_cop) for _ in range(1+max_alp)]
dp[alp][cop] = 0
for cur_alp in range(alp, max_alp+1):
for cur_cop in range(cop, max_cop+1):
for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
if cur_alp >= alp_req and cur_cop >= cop_req:
next_alp, next_cop = cur_alp + alp_rwd, cur_cop + cop_rwd
next_alp = min(next_alp, max_alp)
next_cop = min(next_cop, max_cop)
dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[cur_alp][cur_cop] + cost)
return dp[-1][-1]
Reference
코딩테스트연습 #파이썬 #시간초과 #오류
배울점: 이 코드로 하면 시간 초과도 날 뿐더러 정확성도 보장할 수 없다. 저기 mx = maxx + 1000을 확실히 하려면 1000을 4500으로 바꿔줘야 한다. 왜냐하면 만약 maxx = alp여서 더이상 움직일 필요가 없
velog.io
https://school.programmers.co.kr/learn/courses/30/lessons/118668/solution_groups?language=python3
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'알고리즘 풀이' 카테고리의 다른 글
| [알고리즘] 신고 결과 받기 (0) | 2023.10.16 |
|---|---|
| [알고리즘][X][RE] 행렬과 연산 (1) | 2023.10.15 |
| [알고리즘][X][RE] 등산코스 정하기 (0) | 2023.10.13 |
| [알고리즘][2][X] 조건에 부합하는 중고거래 댓글 조회하기 (0) | 2023.10.12 |
| [알고리즘][X] 두 큐 합 같게 만들기 (1) | 2023.10.09 |