게임공학과 C++ 대비 (중급) - 3주차 5강

3주차 5강은 수로 연결하기라는 문제였다.

문제 내용은 다음과 같다.

처음에는 문제가 이해가 되지 않아 그림판을 이용해 이해를 해보았는데 뭔가 학교에서 풀어봤던 문제라는 느낌이 났었다.

풀이는 기억나지 않았지만 익숙한 문제라는 느낌을 받았다.

그래도 풀이를 어떻게 하는게 좋을까하면서 고민했는데 도저히 모르겠어서 해설을 먼저 보게 되었다.

 해설에서는 동적계획법을 이용해서 문제를 해결했는데 참고해 작성한 코드는 다음과 같다.

d[i][j]를 i번째 파이프에서 부터 j번째 파이프까지 연결하기 위한 비용이라고 했을 때, d[i][j] = min(d[i][k] + d[k + 1][j] + 비용)인것을 이용해 문제를 해결하는 방식이였다.

 

정답을 내는 코드를 보고 이해를 해보면 이해가 되는데 막상 내가 풀때는 풀이 방법이 잘 생각나지 않는다. 앞으로 여러문제를 풀다보면 그래도 익숙해지지않을까라는 생각을 해보며 계속해봐야겠다.