Queue 를 선언하여 현재 위치, 그리고 이동한 위치까지의 움직인 횟 수를 저장하고 반복문을 통해
도착지에 도달하면 도착지까지의 움직임 횟 수를 출력해주면 됩니다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Location7562 {
int x;
int y;
int cnt;
public Location7562(int x, int y, int cnt) {
// TODO Auto-generated constructor stub
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
public class BOJ7562 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
int[] result = new int[tc];
int[] xx = {-1, 1, 2, 2, 1, -1, -2, -2};
int[] yy = {2, 2, 1, -1, -2, -2, -1, 1};
for(int i=0 ;i<tc;i++) {
int l = sc.nextInt();
int n = sc.nextInt();
int m = sc.nextInt();
int destinationX = sc.nextInt();
int destinationY = sc.nextInt();
int[][] map = new int[l][l];
int[][] visit = new int[l][l];
Queue<Location7562> q = new LinkedList<>();
q.offer(new Location7562(n, m, 0));
visit[n][m] = 1;
while(!q.isEmpty()) {
int x = q.peek().x;
int y = q.peek().y;
int cnt = q.poll().cnt;
for(int j=0;j<8;j++) {
int ax = x + xx[j];
int ay = y + yy[j];
if(ax >= 0 && ay>= 0 && ax< l && ay< l && visit[ax][ay] == 0) {
if(ax == destinationX && ay == destinationY) {
result[i] = cnt+1;
q.clear();
break;
}
visit[ax][ay] = 1;
q.offer(new Location7562(ax, ay, cnt+1));
}
}
}
}
for(int i=0;i<result.length;i++) {
System.out.println(result[i]);
}
}
}
while문을 통해 처음 문제를 접근하였지만, 기본 수학 문제로 반복문이 아닌 식을 통해 문제를 풀도록 유도 하는 문제이다.
while문 등 아래와 같이 반복문을 통해 풀게 될 경우 문제의 조건인 (1 ≤ B < A ≤ V ≤ 1,000,000,000)
10억이란 숫자로 반복문을 처리하게 되어 시간 초과가 발생한다.
int cur = 0;
int days = 1;
while(true) {
cur = cur + a;
if(cur >= v) {
System.out.println(days);
return;
}
cur = cur -b;
days++;
}
즉, 수학적 접근으로 아래와 같은 식을 만들 수 있다.
V(나무 막대 높이) / A(오르는 높이) - B (내려가는 높이)
하지만, 위와 같은 식을 처리할 경우 ‘또, 정상에 올라간 후에는 미끄러지지 않는다.’
를 고려해서 식을 바꿔주어야한다.
여기서 접근한 방식은, 높이에서 - 내려가는 높이를 뺀 후, 하루를 올라야하는지 아니면 정상에 도달했는지를 구하는 방식으로 처리하였다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BaekjoonAlgo_2869 {
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int days = (v-b) / (a - b);
if(((v-b) % (a - b)) != 0) {
days++;
}
System.out.println(days);
}
}
추가적으로 Java11에서는 Scanner로 처리 시 시간초과가 발생하여 BufferedReader로 변경하여 제출하였다.
import java.util.Scanner;
public class Main {
static int result = 1;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
refact(n);
System.out.println(result);
}
public static void refact(int x) {
if(x > 0) {
result *=x;
refact(x-1);
}
}
}
