- 금고 . . . . 19 matches
== 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++ || 많이..ㅡㅜ || [금고/문보창] ||
- 금고/문보창 . . . . 7 matches
== 금고 ==
바로 코드 짜면 저번처럼 망해버릴 것만 같아서, 점화식 만들고, 간단히 증명까지 하고 코드를 짰다. 층수 n, 금고수 k 라 할때, 현재 복잡도 O(nk). 구간 값을 저장한다면 메모리와 시간 모두 더 줄일수 있을 것이다.
T(n, k) 를 층수 n 과 금고 수 k 일때의 해라 하자. 여기서 n 을 k 개의 금고를 가지고, T(n, k) 횟수 만에 모두 테스트 할 수 있는 건물의 최대높이라 하자.
층수가 n 인 건물중 해를 찾는 위치에 첫 금고를 떨어뜨린다고 하자. 그러면 건물은 그 위치 아래와 위로 나뉘어지며, 위쪽은 T(b, k) 가 되고, 아래쪽은 T(a, k-1)이 된다. 여기서 a, b는 첫 금고를 떨어뜨린 위치를 기준으로 나뉘어진 위 아래 건물의 층수다. 여기서 문제의 정의에 따라 우리가 구하고자 하는 해는
[금고]
- 금고/조현태 . . . . 3 matches
== [금고/조현태] ==
그런데 왜 하필 떨어지는게 금고인거지?? (맞으면 아프지 않을까??)
[금고]
- 금고/하기웅 . . . . 3 matches
지금보니 생각할게 많네..ㅡㅡ; 금고를 떨어뜨렸을 때 깨진 경우 안깨진 경우에 따라서 다음에 할 수 있는 작업이 틀려지고..
일단 f층에서 s개의 금고가 있으면 s-1개는 f층의 반, 또 그기의 반 이렇게 떨어뜨려보면 되고
s(금고)가 충분하다고 했을 경우를 생각해보면...
- Algorithm/DynamicProgramming . . . . 1 match
== [금고] ==
- BusSimulation/조현태 . . . . 1 match
들떠서 다 적고나서 소스의 설명이 안되있는것을 깨닫고 시급히 수정.. 그런데 어느분이 그사이 페이지를 변경하셔서 눈물을 머금고 다시작성한다.ㅠ.ㅜ
- 경시대회준비반 . . . . 1 match
|| [금고] ||
Found 7 matching pages out of 7540 total pages (5000 pages are searched)
You can also click here to search title.
