[백준] 1669번 멍멍이 쓰다듬기 (자바 풀이)
- 알고리즘 문제 해결(PS)/[백준]
- 2022. 3. 11.
문제
https://www.acmicpc.net/problem/1669
풀이
나는 수학 문제가 너무 어렵다. 이 문제는 수열 문제로 생각을 잘해야 풀 수 있다.
키차이 | Day 1 | Day 2 | Day 3 | Day 4 | Day 5 |
1cm | 1 | ||||
2cm | 1 | 1 | |||
3cm | 1 | 1 | 1 | ||
4cm | 1 | 2 | 1 | ||
5cm | 1 | 2 | 1 | 1 | |
6cm | 1 | 2 | 2 | 1 | |
7cm | 1 | 2 | 2 | 1 | 1 |
8cm | 1 | 2 | 2 | 2 | 1 |
9cm | 1 | 2 | 3 | 2 | 1 |
키차이에 따른 키 크는 과정이다. 잘보면 4cm, 9cm 는 1,2,1 | 1,2,3,2,1 와 같이 ^모양(증가하다가 감소) 수열을 나타내는 것을 확인 할 수 있다.
따라서 2^2, 3^2, 4^2...n^2 처럼 제곱수는 2*n-1 만큼 키크는 과정이 걸리는 것을 확인할 수 있다.
그렇다면 제곱수가 아닌 키차이는 어떻게 계산할 까?
예를 들어 키차이가 7cm인 경우를 살펴보자. 이경우 키차이가 4cm일 때 수열인 1,2,1 에 3cm를 더해서 1,2,(2),(1),1 이렇게 5일이 걸리는 것을 알 수 있다. 이때 사용할 수 있는 가장 큰 수를 집어넣어야 하는데, 키차이가 4cm에서 넣을 수 있는 가장 큰 수는 4의 제곱근인 2다. 따라서 2를 넣고 남은 1을 넣으면 된다.
코드
import java.io.*;
import java.util.*;
public class Baekjoon_1669 {
static int X,Y;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
X = sc.nextInt();
Y = sc.nextInt();
int diff = Y-X;
long n = 0;
if(X==Y) {
System.out.println(0);
return;
}
while(n*n < diff) {
n++;
}
if(n*n != diff) {
n--;
}
long ans = 2*n-1;
diff -= n*n;
while(diff > 0) {
diff -= Math.min(n, diff);
ans++;
}
System.out.println(ans);
}
}
반응형
'알고리즘 문제 해결(PS) > [백준]' 카테고리의 다른 글
[백준] 17822번 원판 돌리기 (자바 풀이) (0) | 2022.03.21 |
---|---|
[백준] 16926번 배열 돌리기 1 (자바 풀이) (0) | 2022.03.21 |
[백준] 16946번 벽 부수고 이동하기4 (자바 풀이) (0) | 2022.03.10 |
[백준] 2239번 스도쿠 (자바 풀이) (0) | 2022.03.10 |
[백준] 2146번 다리 만들기 (자바 풀이) (0) | 2022.03.04 |