22년도 어떤 시험 코테 - 2번째 문제 2차 후기

# 2번의 문제의 2차 후기입니다..

그때 완전 탐색으로 풀었다고 생각했는데 생각 해보니 풀이에 허점이 있습니다.

근데 그뿐이였으면 그냥 그러고 말았을테고,  2차 후기를 배포하지 않았겠죠!ㅋㅋ

그럼 왜했냐?

바로 이문제를 dp로 푸는 데 성공해서 입니다!! ( 테케만 통과했기 때문에 확신할 수 없음.. 애초에 제출할때도  테케는 통과함 ㅋㅋ...)

 

간단하게 원리를 설명하자면

 

# 알고리즘 설명

0. 우리는 줄을 자를 때 하나의 줄을 자를 때는 그냥 자르면 됩니다.

1. 단 두줄을 한 번에 김밥 자르듯이 자른다던가, 3줄을 자르면은 그 줄은 당연히 각각 2의 배수 형태 3의 배수 형태이여 합니다.

2. 이 원리에 착안하여 dp로 접근하였습니다.

 

3. 주어지는 값 times값은 1번 인덱스부터 2줄, 3줄 자르는 cost 비용입니다.

이 줄을 자를 수 있는 조건은 2줄이거나 3줄이거나 등입니다.

즉, 줄 % 2 or 3 등등 == 0의 조건을 성립하면 줄이 잘리는 걸 허용합니다. 이렇게 될 때 해당되는 인덱스에 dp를 min값으로 최신화하면고 dp[n]일 때를 답으로 출력하면 됩니다

* 코드를 한 번 쭉 보시고 설명을 보면 아! 하실 겁니다.

 

#2번 문제 dp로 풀 수 있을듯 하다
def dpCaculate(dp, i, j, times):
    if (i - 1) % (j + 1) == 0:
        dp[(i - 1) * (j + 1)] = min(dp[i - 1] + times[j], dp[(i - 1) * (j + 1)])

    return dp


def solution(n, times):
    dp = [9999 for _ in range(n * (len(times) + 1))]
    dp[0] = 0
    dp[1] = 0

    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + times[0], dp[i])
        for j in range(1, len(times)):
            dpCaculate(dp, i, j, times)

    print(dp)
    answer = dp[n]
    return answer


# n = 5
# times = [2, 4, 5]  # 8
n = 4
times = [2, 3]  # 5
print(solution(n, times))

---

후기

 

이전에 풀이와 비교하면 길이도 짧아지고, 아마 dp로 풀었으므로

효율성 테스트가 있다면 통과할 듯합니다.

물론 정확성이 맞다는 가정입니다만...

이 풀이 맞을 거 같다는 느낌이 듭니다.

코테 당일 집에 가는 길에 생각난 아이디어 풀이는 종이로 썼는데 코드는 지금 올리네요 ㅎㅎ..

코테 당시에 제춯했으면 더좋았으겠지만.. 실력 부족이 아쉽네요

다들 그럼 ㅅㄱ ㅂㅂ