백준 1328번 고층 빌딩

< 백준 1328번 고층 빌딩 - 마포 코딩박 >

사용한 알고리즘: DP


 일렬로 늘어선 N개의 빌딩을 왼쪽(Left), 오른쪽(Right)에서 본 결과를 입력으로 받고, 가능한 배열의 수를 찾는 문제였습니다. DP를 사용하여 해결하였습니다. 풀이를 바로 생각하기 어려운 문제였습니다.

문제풀이는 다음과 같습니다.

(1) N개의 빌딩이 있을때, Left=1&&Right=N 이거나 정반대의 경우, 가능한 배열 수는 1 ( 유일 ) 입니다.

(2) N 개의 빌딩 배열은 N-1 개의 빌딩 배열에서 오는 것을 생각합니다.

(3) N-1 개 빌딩 배열로 -> N 개 빌딩 배열을 만든다고 생각할 때,
    큰 빌딩 1개를 추가한다고 생각하면 헷갈리므로,
    " N-1 개의 빌딩의 높이를 1씩 높여준 뒤, 높이 1 의 제일 작은 빌딩을 추가한다 " 
    라고 생각합니다.

(4) 위의 생각에서, N-1 개의 빌딩에 작은빌딩 1개를 추가로 배열 할 수 있는 위치 수는 N개 입니다.

(5) N-1개의 빌딩 양 끝에 작은 빌딩을 세우면 Left+1 or Right+1 이 됩니다. ( 2자리)
이를 제외한 모든 위치에 작은빌딩을 추가하는 것은 Left와 Right 에 변화를 줄 수 없습니다. ( N-2 자리)

(6) 위의 생각을 제귀함수로 구현하고, 이 과정에서 dp 를 활용해 저장합니다. ( 16번째 줄: 이미 완성된 배열일 경우 return 으로 중복해서 확인하는걸 줄여줘야 시간내에 돌릴 수 있습니다. )

위의 빨간색으로 강조한 생각을 하는 것이 힘들었습니다.