* 빈 상자
책상 위 1 번 박스가 N 개 놓여있다.( N 은 2 이상 )
책상 아래에는 2 번 박스 , 3 번 박스,...가 무한 개 있다.
1 번 박스가 가장 크고 , 다음은 2 번 박스 , 3 번 박스 ...
2 번 박스를 1 번 박스에 넣을 수 는 있지만 3 번 박스를 1 번 박스에 넣을 수는 없다.
즉 i 번 박스에는 i+1 번 박스 만을 넣을 수 있다.
다음 과정을 T 번 반복한다.
■ 몇 개의 1 번 상자마다 2 번 상자 K 개를 집어 넣는다.
■ 몇 개의 2 번 상자마다 3 번 상자 K 개를 집어 넣는다.
■ 몇 개의 3 번 상자마다 4 번 상자 K 개를 집어 넣는다.
■ ...
어떤 상자 안에 아무 것도 없으면 이 상자는 비어 있다고 한다. T번 과정을 반복 한 후 책상 위에는 F 개의 빈 상자가 있다.
다음 그림은 N = 2 , K = 2 , T = 2, F = 5 인 경우의 예이다.
문제는 정수 N, K, T, F 가 주어질 때 책상 위에 있는 총 상자 개수를 구하는 것이다.
입력
첫 줄에 네 개의 정수가 주어진다: N, K, T, F (1 < N , K , T, F < 1 000 000 이고 N < F)
출력
총 상자 개수를 출력한다.
입출력 예
입력
11 8 2 102 출력
115
★★ 이 문제는 조금만 고민해 보면 규칙이 있기 때문에 간단한 한줄 식으로 문제를 해결할 수 있다.
문제의 지문 중 헷갈렸던 부분은 몇개의 상자 에 대한 부분이었는데,
다음 과정을 T 번 반복한다.
■ 몇 개의 1 번 상자마다 2 번 상자 K 개를 집어 넣는다.
■ 몇 개의 2 번 상자마다 3 번 상자 K 개를 집어 넣는다.
■ 몇 개의 3 번 상자마다 4 번 상자 K 개를 집어 넣는다.
■ ...
이 문장을 문제의 그림과 같은 상황으로 생각하고, 값을 대입하여 다시 작성해 보겠다.
N = 2 , K = 2 , T = 2, F = 5 인 경우의 예
다음 과정을 T(=2)번 반복한다.
■ 몇 개의 1 번 상자마다 2 번 상자 K(=2) 개를 집어 넣는다.
↓T(1)
■ 몇 개의 2 번 상자마다 3 번 상자 K(=2) 개를 집어 넣는다.
↓T(2)
■ 몇 개의 3 번 상자마다 4 번 상자 K(=2) 개를 집어 넣는다.
주어진 값에 대해 대입 했음에도 몇개의 상자인지에 대해서는 알 수 없다.
그러므로 현재로써는 몇개의 상자인지는 주어지지 않고 알 수 없는 것이다.
그래서 우리는 문제를 해결하기 위해서 주어진 값들을 이용해 몇 개 의 상자인지를 구해야한다.
우선 임의로 몇개의 상자인지를 정하고 규칙을 찾아보도록 하자.
'T가 2인 경우 = 2번 반복' 하는 경우를 생각해 보면,
(1) N개의 첫번째 상자 중 x 개의 상자에 각각 두번째 상자를 k 개씩 넣으면,
첫번째 상자 중 (N-x) 개의 상자는 빈 상자가 된다.
(2) 두번째 상자는 x 개의 첫번째 상자마다 k 개씩 들어가므로 두번째 상자의 전체 갯수는 x*k 개가 된다.
그러면 x*k 개의 두번째 상자 중 y 개의 상자에 각각 세번째 상자를 k개씩 넣으면,
두번째 상자 중 (x*k-y)개의 상자는 빈 상자가 된다.
(3) 세번째 상자는 y 개의 두번째 상자마다 k 개씩 들어가므로 세번째 상자의 전체 갯수는 y*k 개가 된다.
그러면 y*k 개의 상자는 빈 상자가 된다.
i번째 상자 | 전체 상자의 수 | 빈 상자의 수 | (i+1)번째 상자가 들어간 상자의 수(임의의 수 지정) |
1번째 상자 | N | (N-x) | x |
2번째 상자 | x*k | (x*k-y) | y |
3번째 상자 | y*k | y*k | 없음 |
N = 11 , K = 8 , T = 2, F = 102 인 경우의 예
i번째 상자 | 전체 상자의 수 | 빈 상자의 수 | (i+1)번째 상자가 들어간 상자의 수(임의의 수 지정) |
1번째 상자 | 11 | (11-x) | x |
2번째 상자 | x*8 | (x*8-y) | y |
3번째 상자 | y*8 | y*8 | 없음 |
이제 표를 이용해 식을 도출해 보도록 하자.
빈 상자의 갯수(F) = (N-x) + (x*k-y) + (y*k) 가 된다.
빈 상자의 갯수(F) = N + (k-1)x + (k-1)y 가 될 수 있다.
값을 대입해보면 102 = 11 + (8-1)x + (8-1)y
이것을 계산해 보면 x + y = 13 이라는 것을 알 수 있다.
전체 상자의 수 = N + x*k + y*k = 11 + 8x + 8y 이므로,
위에서 구했던 x + y = 13 이라는 것을 이용하면,
전체 상자의 갯수 = 11 + 8( x + y ) = 11 + 8 * 13 = 115 라는 것을 알 수 있다.
