https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 처음에 dfs로 문제를 풀어야 되나 싶었지만 범위를 보고 dp문제임을 깨달았다. 먼저 초기화 작업이다. 가짓수를 저장하는 2차원 배열 dp이다. int형으로는 표현하기 어렵기때문에 long형으로 선언했다. 그리고 세로로 공사중인 곳을 저장하기 위한 horizontal, 가로로 공사중인 곳을 저장하귀 위한 vertical 배열을 선언해줬..