3차원동적프로그래밍1 백준 1328 c++ -고층 빌딩 [필자 생각] 1차원과 2차원 배열로만 동적프로그래밍을 생각해왔다. 아무리 생각해도 해답이 나오지 않아 자료들을 찾게 되었다. [깨달음] 이 문제는 처음으로 내게 3차원 동적프로그래밍의 사고를 열어준 문제였다. [문제 풀이] D[N][L][R] 의 배열을 만들어 준다. N의 갯수가 증가함에 따라 가장 작은 빌딩을 어디에 놓는지가 핵심인 문제이다. 1. 가장 작은 빌딩을 맨 왼쪽에 넣는다. => D[N-1][L-1][R] 2. 가장 작은 빌딩을 맨 오른쪽에 넣는다 => D[N-1][L][R-1] 3. 가장 작은 빌딩을 중간에 넣는다ㅏ. => D[N-1][L][R]*(N-2) 3번에서 N-2번 곱한 이유는 왼쪽과 오른쪽을 제외하면 나머지 넣을 수 있는 경우의 수가 N-2번이기 때문에 곱해줘야 된다. [소스코.. 2024. 2. 15. 이전 1 다음