지각
1 초 | 256 MB | 3488 | 2541 | 2319 | 74.831% |
---|
문제
창영이는 이번학기에 어떤 교양수업을 듣고 있다. 그런데, 그 교수님은 매우 지각을 자주 하시고 게다가 수업에 지각을 하였을 경우 수업을 일찍 마쳐 주기까지 하는 것을 발견하였다.
창영이는 교수님의 지각시간 0이상의 정수 t와 수업을 일찍 마쳐주는 시간 s 사이에 다음과 같은 관계가 있음을 알았다.
s = t2
문득 창영이는 수업시간 d가 주어졌을 때, 교수님이 얼마나 지각을 할 수 있는지 궁금해졌고, 여러분은 창영이를 도와서 교수님이 지각할 수 있는 최대의 시간을 알아보자. 물론, 교수님이 도착하자마자 수업을 일찍 마쳐서 수업이 끝나는 것도 가능하다. 예를 들어, 수업시간이 6분인 경우, 교수님이 2분 지각을 하면, 4분간 수업을 일찍 마치게 되고, 2+4=6이기 때문에 바로 수업을 끝낼 수 있다. 또 다른 예로, 수업시간이 7분인 경우 교수님이 2분 지각을 하면, 수업을 4분 일찍 마쳐줄 수 있고, 2+4≤7 이므로 가능한 경우가 되고, 교수님이 3분 지각을 하게 되면, 수업을 9분 일찍 마쳐야 되고, 3+9>7 이므로, 교수님이 3분 지각을 하는 것은 불가능하다. 따라서, 교수님은 수업시간이 7분인 경우 교수님은 최대 2분간 지각을 할 수 있다.
입력
창영이가 궁금한 경우의 수 T(1 ≤ T ≤ 100)가 첫 번째 줄에 주어지고, 이어서 T 개의 줄에 수업시간 d(1 ≤ d ≤ 10,000, d는 정수)가 차례대로 주어진다.
출력
수업시간에 따른 교수님이 지각할 수 있는 최대 시간 t를 정수로 구해서 출력한다.
예제 입력 1 복사
5
1
2
5
6
7
예제 출력 1 복사
0
1
1
2
2
알고리즘 분류
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
// 각 테스트 케이스에 대해 반복
for(int i = 0; i < T; i++) {
// 수업 시간 입력 받기
int d = Integer.parseInt(br.readLine());
// 최대 지각 시간 초기화
int max = 1;
// 교수님이 들어오자마자 끝내주는 경우도 고려하여
// 가능한 최대 지각 시간 찾기
while(max + (max * max) <= d) {
max++;
}
// 가능한 최대 지각 시간 출력
// -1 하는 이유는 해당 조건 범위를 벗어난 뒤에야 max 값에 1을 더하는 것을 멈추는데,
// 그렇게 되면 가능한 범위를 하나 넘어가기 때문에 -1을 해줍니다.
System.out.println((max - 1));
}
br.close();
}
}
설명
이 알고리즘 문제는 주어진 수업 시간에 따라 교수님이 얼마나 지각을 할 수 있는지를 계산하는 것입니다. 문제에서 언급되는 관계는 다음과 같습니다: "교수님의 지각 시간 ( t )와 수업을 일찍 마쳐주는 시간 ( s ) 사이에는 다음과 같은 관계가 있습니다: ( s = t^2 ).
문제를 푸는 전략은 다음과 같이 정리할 수 있습니다:
- 주어진 수업 시간 ( d )에 대해 가능한 최대 지각 시간을 찾습니다.
- 최대 지각 시간을 구하는 방법은 다음과 같습니다:
- ( t ) 값을 1부터 시작해서 증가시키면서 ( s = t^2 )가 ( d ) 이하인 경우까지 반복합니다.
- ( s )가 ( d ) 이하인 경우, ( t ) 값을 1씩 증가시키면서 ( s = t^2 )를 만족하는 최대 ( t ) 값을 찾습니다.
- ( s )가 ( d ) 이상이 되는 시점에서 반복문을 종료합니다.
- 찾은 최대 ( t ) 값에서 1을 빼서 교수님이 지각할 수 있는 최대 시간을 구합니다.
이전에 작성한 코드는 위 전략을 구현한 것입니다. BufferedReader를 사용하여 입력을 읽고, 각 테스트 케이스에 대해 반복하면서 주어진 수업 시간에 따른 최대 지각 시간을 계산하고 출력합니다.
이러한 접근 방식은 문제에서 주어진 관계식을 활용하여 교수님이 지각할 수 있는 최대 시간을 효율적으로 계산할 수 있도록 합니다.
위의 알고리즘은 다음과 같이 동작합니다:
- 먼저, 주어진 수업 시간 (d)에 대해 가능한 최대 지각 시간을 찾습니다.
- 가능한 최대 지각 시간을 구하는 방법은 (t) 값을 1부터 시작해서 증가시키면서 (s = t^2)가 (d) 이하인 경우까지 반복하는 것입니다. 이때, (s)는 교수님이 수업을 끝내는 시간을 나타냅니다.
- (s)가 (d) 이하인 경우, (t) 값을 1씩 증가시키면서 (s = t^2)를 만족하는 최대 (t) 값을 찾습니다.
- (s)가 (d) 이상이 되는 시점에서 반복문을 종료합니다.
- 찾은 최대 (t) 값에서 1을 빼서 교수님이 지각할 수 있는 최대 시간을 구합니다.
이러한 접근 방식은 문제에서 제공한 관계식 (s = t^2)을 활용하여 교수님이 지각할 수 있는 최대 시간을 효율적으로 계산합니다. 이 알고리즘은 수업 시간에 따라서만 영향을 받으며, 수업 시간이 주어졌을 때 지각할 수 있는 최대 시간을 계산합니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 암호 만들기 - 1759번 (0) | 2024.06.13 |
---|---|
[백준] 단어나누기 - 1251번 (0) | 2024.06.12 |
[백준] 좋은 암호 - 2061번 (0) | 2024.06.12 |
[백준] 타임머신 - 1440번 (1) | 2024.06.12 |
[백준] 블랙잭 - 2798번 (0) | 2024.06.12 |