[2022 KAKAO TECH INTERNSHIP] Q3. 코딩 테스트 공부 (C++, Python, Java)

문제 링크

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

 

예상 난이도

G3

 

알고리즘 분류

다이나믹 프로그래밍

 

풀이

일단 DP이긴 합니다. DP이긴 한데 풀이를 보는 입장에서 중요한건 이 문제가 DP란걸 아는 것보다 문제를 보고 DP란걸 어떻게 알아냈는지를 착안해냈는지를 아는거라고 생각합니다. 저는 개인적으로 문제가 익숙한 형태여서 일단 D[i][j] = 알고력 i, 코딩력 j를 달성하는데 필요한 최소 시간으로 테이블을 정의하고 DP가 가능한지, 즉 점화식이 세워지는지를 확인해봤습니다. 이건 상대적으로 경험이 많은 저의 경우이고 다소 경험이 많지 않은 상황에서 풀이를 접근하는 과정을 생각해보면 코딩력이 없다 치고 능력치를 1개만 놓고 문제를 풀어보려고 하면 knapsack DP 느낌이 나기 때문에 이 사고를 확장시켰을수도 있겠다 싶습니다. 만약 2차원 DP도 해본적 없고 knapsack DP도 몰랐다면 아쉽지만 이 문제를 보고 DP를 착안해낼 수 있는 방법은 없었을 것 같습니다. 결국 문제를 많이 풀어보는 방법 밖에는 없는 것 같네요.

 

아무튼 DP라는걸 알았다고 치면 DP 문제에서는 테이블의 정의, 점화식, 초기값, 채우는 순서를 잘 생각해야 합니다. 테이블의 정의는 앞에서도 봤지만 다소 자명하게 정해지고 점화식도 문제를 풀거나 혹은 알고력/코딩력을 1 올리는 조건으로부터 비교적 쉽게 얻어낼 수 있습니다. 초기값도 D[alp][cop] = 0으로 두면 됩니다.

 

채우는 순서 또한 문제의 상황 자체가 각 칸은 자신의 좌상단에 위치한 칸으로부터 값을 받아오기 때문에 크게 고민할게 없고 그냥 (0,0) -> (0,1) -> (0,2) 이렇게 각 행에서 왼쪽에서 오른쪽으로, 행은 윗쪽부터 채워나가면 됩니다.

 

그런데 한 가지 짚고 넘어갈 점이 있는데, dp에서 bottom-up으로 테이블을 채울 때 2가지 방법을 생각할 수 있습니다. BOJ 1463번: 1로 만들기 문제로 예를 들어보면 첫 번째 방법은 d[i] = min(d[i/3], d[i/2], d[i-1])+1 이라는 식을 가지고 각 칸을 채우는 방법입니다.

 

두 번째 방법은 d[i] 값이 확정된 후 d[i+1], d[2i], d[3i] 칸의 값을 갱신하는 방법입니다. 맨 처음에는 d[1] = 0으로 시작해 d[2], d[3]을 갱신하고 다음에는 d[2] = 1이 확정된 후 d[3], d[4], d[6]을 갱신합니다.

 

이 두 가지 방법은 모두 올바른 답을 주지만 이 문제에서는 두 번째 방법으로 구현을 하는게 편합니다. 이게 무슨 의미인지를 이해하기 위해 DP 식을 다시 살펴보면, 우리는 구한 점화식을 가지고 D 테이블을 채웁니다. 우리는 알고력/코딩력 각각이 정확히 alp_max/cop_max가 되는게 목표가 아니라 각각 alp_max/cop_max 이상이 되는 것이 목표이니 최종적인 답은 D[alp_max][cop_max]가 아니라 D[alp_max+1][cop_max], D[alp_max+2][cop_max] 와 같이 i >= alp_max, j >= cop_max인 D[i][j]중 최솟값이 정답입니다. 그런데 이 때 테이블의 크기를 얼마로 잡아야 할까요?

 

극악의 예시를 보면 알고력/코딩력이 각각 2400까지 도달할 수 있습니다. 즉 테이블을 2400 ⨉ 2400으로 잡아야 함을 의미합니다. 이렇게 되면 O(2400 ⨉ 2400 ⨉ 100)으로 시간초과가 날 수 있습니다. 물론 한 쪽이 2400 가까이 가면 다른쪽은 150 근방일거라 약간의 최적화를 하면 실제로는 2400 ⨉ 150 정도의 칸을 쓰도록 할 수는 있지만 이렇게 하기보다는 D 테이블의 정의를 살짝 바꿀 필요가 있습니다. 참고로 앞에서 (아마 의도하지 않았을) 이라는 단서를 둔 이유는 테스트케이스 중에 이렇게 극악인 테스트케이스가 없었기 때문이긴 합니다만 어쨌거나 이런 경우를 고려할 필요가 있습니다.

 

테이블의 정의를 어떻게 바꿀 수 있냐면 D를 alp_max ⨉ cop_max로 잡고 아래쪽/오른쪽 경계에 한해서만 알고력이 정확히 alp_max인게 아니라 alp_max 이상인 것으로, 혹은 코딩력이 정확히 cop_max인게 아니라 cop_max 이상인 것으로 바꾸면 됩니다. 이렇게 되면 alp_rwd/cop_rwd를 받아서 alp_max/cop_max를 넘어서면 그냥 alp_max/cop_max인걸로 제한을 걸어버릴 수 있습니다. 이걸 두 번째로 소개한 테이블을 채우는 방법에서는 그냥 값을 넣어줄 때 i+alp_rwd, j+cop_rwd가 alp_max, cop_max보다 큰지만 확인해서 적절하게 처리를 해주면 되는데, 첫 번째로 소개한 테이블을 채우는 방법에서는 다른 D[i][j]를 계산할 땐 그냥 D[i-alp_rwd][j-cop_rwd]만 보다가 D[alp_max][j]를 계산할 때에는 D[alp_max][j-cop_rwd], D[alp_max-1][j-cop_rwd], ...., D[alp_max-aop_rwd][j-cop_rwd]를 모두 확인하는 방식으로 예외처리를 해줘야 해서 코드가 다소 복잡해집니다.

 

그래서 저는 방법 2를 이용했으나 방법 1로 구현을 해보는 것도 좋은 연습이 될 것 같습니다.

 

코드(C++)

 

코드(Python)

 

코드(Java)