2022 KAKAO TECH INTERNSHIP - 3. 코딩 테스트 연습

https://jaimemin.tistory.com/2181 글을 참고하였습니다.

 

• 코딩테스트 세미나 일요일 오후 2시-3시 (문제, 아이디어) - 2022 kakao tech internship 섬머문제 3. 코딩테스트 공부

알고력 alp와 코딩력 cop에 도달하는 최단 시간을 dp[alp][cop]로 하는 2차원 배열을 만듭니다. 문제에서는 모든 문제를 다 풀수 있는 알고력과 코딩력에 도달하라고 합니다. 그래서 모든 문제를 순회하면서 alp_max와 cop_max을 고릅니다. 어떤 문제를 풀어가면서 최소한의 시간을 쓸 수 있을까요? 이건 알고력과 코딩력이 나눠진 상태에서 여러 문제를 풀어서 alp_max와 cop_max 지점에 가는 것입니다.

• 문제를 풀어서 실력을 올리지 않는다면 공부를 할것이고,
• 문제를 풀어서 실력을 올린다면 우선 그문제를 풀어야할 실력이 갖춰져 있어야 될 것입니다.

초기의 알고력 을 나타내는 alp 와 초기의 코딩력을 나타내는 cop가 주어지는데 이 범위는 0이상 150이하입니다. 동적계획법을 풀때는 그 목표가 동적이라는 걸 인지할 필요가 있습니다. 그 말인즉슨, 어떤 상태(dp[i][j])가 의미하는게 그 값이 서로 다른 경우의 조합으로 만들어진다는 말입니다. 

 

이 문제에서는 상태가 알고력과 코딩력이고, 각각의 능력치가 달라서 (dp[i][j] 의 업데이트 되는 조건이 따로 있음) 그렇게 됩니다. 표를 그려서 설명해보면 다음과 같습니다. 표의 크기는 임의로 정했습니다.

 

1. 문제가 없는 상황이다. 지금 알고력 코딩력은 0, 0 이다.

0	1	2	3	4	5
1	2	3	4	5	6
2	3	4	5	6	7
3	4	5	6	7	8
4	5	6	7	8	9

2. 현재의 알고력 및 코딩력이 0, 0 일때, 1문제([1, 1, 1, 1, 1])가 추가된다면 각 위치에서의 소요시간은 아래와 같이 변한다.

0	1	2	3	4	5
1	2	3	4	5	6
2	3	3	4	5	6
3	4	4	4	5	6
4	5	5	5	5	6

3. 현재의 알고력 및 코딩력이 0, 0일때, 1문제가 더 추가된다면(총 [1, 1, 1, 1, 1], [4, 5, 2, 1, 1]) 각 위치에서의 소요시간은 아래와 같이 변한다. 밑줄 친 값이 우리가 원하는 목표 알고력, 코딩력에 도달하는 시간이다.

• 물음표위치는 어떻게 줄어들까?
• 목표 알고력 및 코딩력을 넘어서 dp배열의 크기를 정했다. 그럴 경우가 있을까?

0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	3	4	5	6	7
3	4	4	4	5	6	7
4	5	5	5	5	6	7
5	6	6	6	6	6	7

4. 3문제([1, 1, 1, 1, 1], [4, 5, 2, 1, 1], [2, 2, 1, 2, 1])가 있다고 생각해보자. 밑줄 친 숫자부터 새로운 문제를 풀어 알고력과 코딩력을 늘릴수 있다면 물음표가 붙은 숫자들을 최소값으로 업데이트 할수 있을까? 아래에 최소로 업데이트 할수 있는 숫자들을 표시해두었다. 최소시간으로 업데이트가 가능한지 생각해보자.

0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	3	4	5	6	7
3	4	4	4	5?	6?	7?
4	5	5	5	5?	6?	7?
5	6	6	6	6?	6?	7?

이는 아래처럼 업데이트 될 수 있다.

0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	3	4	5	6	7
3	4	4	4	4	6	7
4	5	5	5	5	5	5
5	6	6	6	6	6	6

그러면 이제 확장시켜봐야할때,

• 즉, 우리는 어떤 경우든 dp를 통해서 답을 낼수 있어야 되므로 dp배열이 나타내는 알고력과 코딩력이 최대 한도일 때를 만들어줘야된다. 즉, 151x151은 되어야 모든 경우를 표현할 수 있다.

그럼 이제 2차원 배열을 채운 아이디어를 그대로 이용할 수 있다.

• 문제를 안푼다면, 시간 1로 공부를 해서 알고력, 혹은 코딩력을 1씩 올린다
• 문제를 푼다면
  • 풀수있는 문제들만 풀어서
  • 도달하는 최소 시간을 계산할 것

파이썬 코드

import sys
sys.setrecursionlimit(int(1e8))

def dfs(algo, coding, problems):
    if algo >= alp_max and coding >= cop_max:
        return 0
    
    if dp[algo][coding] != -1:
        return dp[algo][coding]
    
    dp[algo][coding] = 987654321
    dp[algo][coding] = min(dp[algo][coding], dfs(min(alp_max, algo+1), coding, problems) + 1)
    dp[algo][coding] = min(dp[algo][coding], dfs(algo, min(cop_max, coding+1), problems) + 1)
    
    for i in range(len(problems)):
        if problems[i][0] > algo or problems[i][1] > coding:
            continue
        dp[algo][coding] = min(dp[algo][coding], dfs(min(alp_max, algo+problems[i][2]), min(cop_max, coding+problems[i][3]), problems) + problems[i][4])
        
    return dp[algo][coding]

def solution(alp, cop, problems):
    global dp, alp_max, cop_max
    answer = 0
    alp_max, cop_max = 0, 0
    
    for i in range(len(problems)):
        alp_req, cop_req = problems[i][0], problems[i][1]
        if alp_max < alp_req:
            alp_max = alp_req
        if cop_max < cop_req:
            cop_max = cop_req
            
    bnd_alp, bnd_cop = 160, 160
    dp = [[-1]*(bnd_alp) for _ in range(bnd_cop)]
    answer = dfs(alp, cop, problems)
    return answer