BOJ 1328 고층 빌딩

모르겠어서 백준님의 강의 슬라이드 풀이를 봤는데, 일단 d[N][L][R]로 설정한 것은 같았지만 아예 접근 방식이 다르다...

나로써는 전혀 생각조차 못해서 그런지(어쩌면 생각을 안 한 것일 수도...) 감탄이 나오는 방식인데, 기본이 되는 아이디어는
1. 빌딩이 1~N까지의 빌딩이 있으면 2~N까지의 빌딩으로 만들 수 있는 모든 경우를 만들고, 2. 거기다 남아있는 높이 1의 빌딩을 넣어보면서 경우의 수를 세는 것이다!

높이 1의 빌딩은 높이가 가장 작기때문에, 1을 넣는 방법은 이미 2~N으로 만들어 놓은 어떤 경우에도 항상 동일한 규칙으로 적용되어 경우의 수를 구하기가 용이하다.

처음엔 왜 이렇게 하나 이해가 잘 안되었는데, 이렇게 하면 당연히 모든 경우의 수를 커버할 수 있을 뿐만 아니라 경우의 수를 세는 규칙(점화식)도 알 수 있어서 좋은 것 같다.

좀 더 생각해보고 정리해서 풀어봐야겠다.

일단 풀었는데, 처음에 틀리길래 int를 long long으로 바꾸었더 AC를 받았다. 분명 중간 중간에 일일이 1e9+7로 나누어주는데 왜 integer overflow가 나지? 이렇게 한참 고민하다가 깨달았다!

바로 ret+=building(n-1, l, r)*(n-2) 이 부분이다! n-2만큼 곱해주니 integer overflow가 날 수 있는 것이다. 그래서 이것을 for문으로 고쳐서 n-2번 더하면서 계속 나눠줬는데, 그러니 시간이 더 오래 걸린다. 내가 듣기로는 일부 연산의 경우 나누기였나? %였나 많이 하면 시간에 꽤 영향을 준다고 들었는데, 그래서 그런 것 같다. 컴퓨터 구조 열심히 공부했으면 왜 그런지 알았을 텐데 일단 나중에 공부 해봐야겠고, dp 열심히 해야겠다.