어제 저녁에 고층 빌딩을 열어서 읽다가 잠들었다. 그래서 일어나자마자 풀고 풀이를 적었다. 글 [BOJ 1328] 고층 빌딩 요즘 학교 OJ에다가 USACO 문제들을 번역해서 하나 둘씩 올리고 있다. 어제는 해커컵 예선 A번 번역한 거에다가 TC를 추가하고 정답 코드를 재채점 돌렸다. 그런데 웬걸, 서버가 터졌다. 아침에 일어나니 다시 잘 돌아가고 있길래 재채점을 다시 돌렸다. 웬걸, 다시 터졌다. 호스팅 업체의 문제인지, OJ의 문제인지 뭔지 모르겠다. 고작 코드 2개 재채점 돌리는데 터지다니... 그래서 Mountain Climbing을 오늘 올리려고 했는데 아직도 못 올리고 있다. P2 짜리를 하나 풀었는데... 구현만 몇 시간 걸린 것 같다. 힘들다... 아무래도 깔끔하게 다시 풀어볼 필요가 있다..

문제 링크 질문은 언제나 환영입니다. 3가지 풀이법이 나오네요. 글에는 없는 자신만의 풀이법이 존재하신다면 알려주세요! 두 가지 풀이법은 $O(n^3)$짜리 풀이이고, 한 가지 풀이법은 $O(n^2)$짜리입니다. 풀이 더보기 문제에서 구해야 하는 것은 조건을 만족하는 배치의 수입니다. 세세한 배치의 성질들에 대해 알아볼 방법은 떠오르지 않고, 작은 케이스부터 풀다 보면 패턴이 보이기 때문에 동적 계획법을 시도해볼 수 있습니다. 3차원 동적 계획법 $B(x,y,z):=x$개의 빌딩 중 왼쪽에서 $y$개, 오른쪽에서 $z$개만 보이는 경우의 수 위와 같이 정의하는 것은 아주 자연스럽습니다. 점화식을 도출할 때는 $B(x-1,\cdots )$와의 관계를 우선 생각 해봅시다. 새로 생긴 가장 긴 막대기를 어디다..