BackLinks of 금고

• Algorithm/DynamicProgramming
       == [금고] ==
• 경시대회준비반
       || [금고] ||
• 금고
       == About [금고] ==
       N층 빌딩이 있다. 이 빌딩의 F층은 금고를 떨어뜨렸을때에 부서지는 최소층이다. 다시 말하면, F층을 포함하여 그위의 층에서 금고를 떨어뜨리면 무조건 부서지며, F층의 아래층에서 금고를 떨어뜨릴 떄에는 금고는 절대 부서지지 않는다.(N층에서도 부서지지 않으며, 1층에서도 부서질수도 있다.)
       새로 개발한 금고의 견고함을 측정해서 광고하려고 하는데, 금고 K개를 가지고 이 빌딩의 F층이 몇 층인지를 알고 싶다. 가능한 방법은 임의의 층에서 직접 금고를 떨어뜨리고 그 결과를 확인 하는 것 뿐이다. 물론, 부서진 금고는 다시 사용할수 없으며 부서지지 않았다면 다시 사용할수 있다.
       이런상황에서 K개의 금고를 가지고 F층이 몇층이던 간에 F층을 알아낼수 있는 최소한의 금고 낙하 획수를 E(N,K)이라 하자. 예를 들어 K = 1이라면 F를 알아내기 전에 금고가 부서지면 안되기 때문에 1층부터 차례대로 올라가면서 금고를 낙하해야 하며 많아야 N번이면 F층을 알아 낼수 있다. 따라서 E(N, 1) = N이다. 건물의 층수를 나타내는 정수 N과 금고의 개수를 나타내는 정수 k가 주어 졌을때, E(N,K)를 계산하는 프로그램을 작성하시오.
       입력은 표준 입력(standard input)을 통해 받아들인다. 입력의 첫줄에는 테스트 케이스의 개수 T(1 <= T <= 10)가 주어진다. 각 테스트 케이스는 한줄에 빌딩 전체 층수와 금고의 개수를 의미하는 두개의 정수 N과 K(1 <= K <= N <= 500)가 순서대로 주어진다.
        || 김상섭 || C++ || 많이..ㅡㅜ || [금고/김상섭] ||
        || 하기웅 || C++ || 10분ㅡㅡ; || [금고/하기웅] ||
        || [조현태] || C++ || ? || [금고/조현태] ||
        || [문보창] || C++ || 많이..ㅡㅜ || [금고/문보창] ||
• 금고/조현태
        == [금고/조현태] ==
        그런데 왜 하필 떨어지는게 금고인거지?? (맞으면 아프지 않을까??)
       [금고]
• 금고/문보창
       == 금고 ==
       바로 코드 짜면 저번처럼 망해버릴 것만 같아서, 점화식 만들고, 간단히 증명까지 하고 코드를 짰다. 층수 n, 금고수 k 라 할때, 현재 복잡도 O(nk). 구간 값을 저장한다면 메모리와 시간 모두 더 줄일수 있을 것이다.
       T(n, k) 를 층수 n 과 금고 수 k 일때의 해라 하자. 여기서 n 을 k 개의 금고를 가지고, T(n, k) 횟수 만에 모두 테스트 할 수 있는 건물의 최대높이라 하자.
       층수가 n 인 건물중 해를 찾는 위치에 첫 금고를 떨어뜨린다고 하자. 그러면 건물은 그 위치 아래와 위로 나뉘어지며, 위쪽은 T(b, k) 가 되고, 아래쪽은 T(a, k-1)이 된다. 여기서 a, b는 첫 금고를 떨어뜨린 위치를 기준으로 나뉘어진 위 아래 건물의 층수다. 여기서 문제의 정의에 따라 우리가 구하고자 하는 해는
       [금고]

You can also click here to search title.