𝙰𝚕𝚐𝚘𝚛𝚒𝚝𝚑𝚖/𝙱𝚊𝚎𝚔𝚓𝚘𝚘𝚗
[백준/Java] 멍멍이 쓰다듬기 1669
해버니
2023. 11. 7. 08:30
반응형
문제

귀여운 문제다..
원숭이가 강아지를 쓰다듬다니 너무 귀여운걸..?
귀여웍!!!
풀이
첫째날과 마지막날은 1cm만 자랄 수 있다고 한다.
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
10cm 차이 : 1 2 3 2 1 1
11cm 차이 : 1 2 3 2 2 1
12cm 차이 : 1 2 3 3 2 1
13cm 차이 : 1 2 3 3 2 1 1
14cm 차이 : 1 2 3 3 2 2 1
15cm 차이 : 1 2 3 3 3 2 1
16cm 차이 : 1 2 3 4 3 2 1
17cm 차이 : 1 2 3 4 3 2 1 1
...
이런식으로 숫자가 증가할 것이다.
그래서 규칙성 찾기 -> 로직 구현하기로 문제를 풀었다.
sqrt까진 생각했는데 그 다음에 어떻게 진행할 지 몰라서 다른 블로그글에서 힌트를 얻어서 풀었다.
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Heap_11296 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long monkey = Integer.parseInt(st.nextToken()); // 원숭이 키
long dog = Integer.parseInt(st.nextToken()); // 강아지 키
long subtract = dog - monkey; // 키 차이
long sqrt = (long) Math.floor(Math.sqrt(subtract)); // 키 차이의 제곱근
subtract -= sqrt*sqrt; // 키 차이 - 제곱근^2
long answer = sqrt>0 ? sqrt * 2 - 1 : 0; // 만약 원숭이와 강아지의 키 차이가 0이면 answer 0 설정
if (subtract > sqrt) { // 한 제곱근과 다음 제곱근 사이의 중간보다 뒤에 있으면
answer += 2;
} else if (subtract > 0 && subtract <= sqrt) { // 한 제곱근과 다음 제곱근 사이의 중간보다 앞에 있으면
answer += 1;
}
System.out.println(answer);
}
}
반응형