Logo냥냠감자기술 블로그
Skip to Content
AlgorithmDP (31)고층빌딩
작성일: 2024-01-12

문제

백준 1328 - 고층빌딩 

  • 난이도: 플레5
  • 알고리즘: DP

코드

#include <iostream> #include <cstring> using namespace std; int calCase(int buildingNum, int leftSeen, int rightSeen, int cache[101][101][101]) { if(leftSeen==1 && rightSeen==1) { if(buildingNum==1) { return 1; } else { return 0; } } if(buildingNum==0 || buildingNum+1<leftSeen+rightSeen) { return 0; } if(leftSeen<1 || rightSeen<1) { return 0; } int& ret=cache[buildingNum][leftSeen][rightSeen]; if(ret!=-1) return ret; ret=0; ret=(ret+(long long)calCase(buildingNum-1, leftSeen-1, rightSeen, cache))%1000000007; ret=(ret+(long long)calCase(buildingNum-1, leftSeen, rightSeen-1, cache))%1000000007; ret=(ret+(long long)calCase(buildingNum-1, leftSeen, rightSeen, cache)*(buildingNum-2))%1000000007; return ret; } int main() { int buildingNum, leftSeen, rightSeen; cin>>buildingNum>>leftSeen>>rightSeen; int cache[101][101][101]; memset(cache, -1, sizeof(cache)); cout<<calCase(buildingNum, leftSeen, rightSeen, cache); }

회고

처음엔 조금 막막했지만, 빌딩을 높이 순서대로 어디에 배치하면 왼쪽과 오른쪽에서 보이는 빌딩 수가 어떻게 고민할지 손으로 대입해보면서 고민해보니 해결 방법이 보였다. cache[빌딩 수][왼쪽에서 보이는 빌딩 수][오른쪽에서 보이는 빌딩 수]=sum(cache[빌딩 수-1][왼쪽에서 보이는 빌딩 수-1][오른쪽에서 보이는 빌딩 수] + cache[빌딩 수-1][왼쪽에서 보이는 빌딩 수][오른쪽에서 보이는 빌딩 수-1] + cache[빌딩 수-1][왼쪽에서 보이는 빌딩 수][오른쪽에서 보이는 빌딩 수]*(빌딩 수-2)) 로 구할 수 있다.
기저 사례는 함수 위에 표시한 바와 같다. 역시 그래도 DP가 가장 자신 있는 것 같다. 조금 시간을 두고 천천히 생각해보면 풀이 방법을 찾을 수 있는 것 같다. 사실 이런 방식의 영감을 얻어 해결하는 방식 대신에 조금씩 답에 근접해가는 방식으로 문제를 풀고 싶다. 지금은 약간 특히 어려운 문제일수록 반짝이는 영감에 의존한 문제 풀이를 하는 느낌이다.