문제
https://www.acmicpc.net/problem/1011
풀이
시작지점과 도착지점이 도달할때, 반드시 1광년으로 해야한다고 했고, 공간 이동 장치 횟수의 최솟값을 도출해야한다.
거리 - (광년이동)
1 - (1)
2 - (1 1)
3 - (1 1 1)
4 - (1 2 1)
5 - (1 2 1 1)
6 - (1 2 2 1)
...
9 - (1 2 3 2 1)
...
12 - (1 2 3 3 2 1)
...
16 - (1 2 3 4 3 2 1)
...
20 - (1 2 3 4 4 3 2 1)
그러면 거리에 따른 이제 공간 이동 장치 작동 횟수를 보도록 하겠다. 개수는 작동 횟수에 해당하는 종류의 개수를 뜻한다. 예를 들어, 3 ~ 4에 해당하는 거리(거리 개수)는 3번 작동(작동 횟수)해야하며, 3번 작동해야하는 거리의 개수(종류)는 2가지이다.
| 거리 | 1 | 2 | 4 | 6 | 9 | 12 | 16 | 20 |
| 거리개수 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
| 작동 횟수 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
자 그러면, 거리가 제곱수를 기준으로 빨간색을 주목하면 패턴이 보인다.
우리는 거리에 해당하는 거리개수만 구하면 작동 횟수를 구할 수 있다. 그러면 어떻게 구할 수 있을까? 시그마 공식을 사용한다.
우리가 1부터 10까지 더한 값은 55라고 알고 있다. 시그마 공식으로 어떻게 도출이 되는가.
1부터 k까지 더한 값은 k * (k + 1) / 2이다. 그래서 k = 10 => 55가 나오게 된다.
표에서 거리의 개수를 보면 1 1 2 2 즉 2개씩 더하고 있다. 즉, (k * (k + 1) / 2) * 2이므로, k * (k + 1)이다.
k = 1이면, 거리 : 2
k = 2이면, 거리 : 6
k = 3이면, 거리 : 12
k = 4이면, 거리 : 20
그러면 y - x(거리)에 해당하는 k값을 구한다.
k^2보다 같거나 작다면 (2 * k) - 1이고,
그게 아니라면 (2 * k)이다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
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());
StringBuilder sb = new StringBuilder();
for (int test = 1; test <= t; test++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long x = Long.parseLong(st.nextToken());
long y = Long.parseLong(st.nextToken());
//이동거리
long dist = y - x;
long k = 1;
//k를 구하기
while (true) {
if (k * (k + 1) >= dist) {
break;
}
k += 1;
}
//공간 이동 장치 작동 횟수의 최솟값
long answer = -1;
if (dist > (k * k)) {
answer = 2 * k;
}
else {
answer = (2 * k) - 1;
}
sb.append(answer).append("\n");
}
//출력
System.out.print(sb);
br.close();
}
}'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 백준 12865: 평범한 배낭 - Java (0) | 2025.06.22 |
|---|---|
| [Baekjoon] 백준 1092: 배 - Java (0) | 2024.10.17 |
| [Baekjoon] 백준 7662: 이중 우선순위 큐 - Java (0) | 2024.09.22 |
| [Baekjoon] 백준 9935: 문자열 폭발 - Java (0) | 2024.09.19 |
| [Baekjoon] 백준 1038: 감소하는 수 - Java (0) | 2024.09.16 |