타일 면적표
문제
어느 타일 공장은 가로와 세로의 길이가 모두 자연수인 타일을 찍어낸다. 가로의 길이로 쓸 수 있는 값은 1부터 N까지이고, 세로의 길이로 쓸 수 있는 값도 1부터 N까지다. 따라서 공장이 찍어낼 수 있는 타일의 종류는 모두 N×N가지다.
각 타일의 면적은 (가로의 길이 × 세로의 길이)로 계산된다. 공장의 검수 담당자는 N×N가지 타일의 면적을 모두 적은 뒤에, 적어 둔 값들을 작은 것부터 큰 것까지 오름차순으로 줄을 세운다. 이때 면적이 같은 타일이 여러 가지 있어도 각각을 따로 세어 줄에 넣는다. 그래서 줄에 놓이는 값은 언제나 N×N개다.
이렇게 줄을 세웠을 때, 앞에서부터 K번째에 놓이는 면적을 구하는 프로그램을 작성하여라.
예를 들어 N=3이라고 해보자. 이때 찍어낼 수 있는 타일은 모두 9가지이며, 각 타일의 면적은 다음의 표와 같다.
| 가로의 길이 | 세로가 1 | 세로가 2 | 세로가 3 |
|---|---|---|---|
| 1 | 1 | 2 | 3 |
| 2 | 2 | 4 | 6 |
| 3 | 3 | 6 | 9 |
표에 적힌 9개의 값을 오름차순으로 줄 세우면 다음의 표와 같다.
| 순서 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 면적 | 1 | 2 | 2 | 3 | 3 | 4 | 6 | 6 | 9 |
따라서 K=7이라면 정답은 6이다. 같은 예시에서 K=2라면 정답은 2이고, K=9라면 정답은 9이다.
줄을 전부 세우지 않고도 답을 짚어 볼 수 있다. 어떤 값을 기준으로 잡고, 면적이 그 값 이하인 타일이 몇 가지인지만 세어 보는 것이다. 앞의 N=3 예시에서 기준을 1부터 9까지 바꿔 가며 세어 보면 다음의 표와 같다.
| 기준 면적 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 면적이 기준 이하인 타일의 수 | 1 | 3 | 5 | 6 | 6 | 8 | 8 | 8 | 9 |
K=7인 경우를 이 표에서 찾아 보자. 기준이 1, 2, 3, 4, 5일 때는 세어 둔 수가 7보다 작으므로 7번째 값이 아직 나오지 않았다. 기준이 6이 되면 세어 둔 수가 처음으로 7 이상이 되므로, 7번째에 놓이는 면적은 6이다.
N이 커지면 줄에 놓이는 값이 N×N개가 된다. N이 100,000이면 그 수가 100억 개이므로, 면적을 전부 적어서 정렬하는 방법으로는 시간 안에 답을 구할 수 없다.
입출력 예시
예시 1
입력
3 7
출력
6
예시 2
입력
2 2
출력
2
예시 3
입력
10 50
출력
24
입력 조건
가장 먼저 타일의 길이로 쓸 수 있는 가장 큰 값 N이 자연수로 주어진다. (N은 100,000보다 작거나 같은 자연수다.)
이어서 다음 줄에 몇 번째 면적을 구할 것인지를 나타내는 K가 자연수로 주어진다. K는 1 이상 1,000,000,000 이하의 자연수이며, 줄에 놓이는 값의 개수인 N×N보다 크지 않다.
따라서 입력은 두 줄이며, 각 줄에 자연수가 하나씩 들어 있다.
출력 조건
앞에서부터 K번째에 놓이는 면적을 첫째 줄에 자연수로 출력한다. 이 값은 1 이상 10,000,000,000 이하다.
출력하는 수 뒤에는 줄바꿈 하나만 붙는다. 수 앞이나 뒤에 공백을 붙이지 않고, 줄바꿈 뒤에 빈 줄을 더 붙이지도 않는다.
요구사항
- 면적이 같은 타일이 여러 가지 있어도 각각을 따로 세어 줄에 넣습니다
- 줄에 놓이는 값은 언제나 N×N개입니다
- K는 N×N보다 크지 않습니다
- 면적을 모두 적어서 정렬하는 방법으로는 시간 안에 답을 구할 수 없습니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 2
2
3 7
6
10 50
24
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.