[문제해결을 위한 창의적 알고리즘] 숙직 선생님 (고급 p.97)
이 문제는 책에서 여러가지 형태로 다루고 있으므로, 추가적인 설명은 적지 않도록 하겠다. 가장 마지막 방법이 가장 효율적인 방법이므로, 그 방법을 나름의 방법으로 코딩해 보았다. 개인적으로는 책에 설명된 것보다 더 직관적인 코드라는 생각이 든다.
간략 설명
1) 현재 위치에서 3가지 능력 각각에 대해 갈 수 있는 위치를 업데이트 한다.
2) 해당 위치에 이미 업데이트 된 값이 있으면 작은 경우에만 업데이트 한다.
3) 만약 b의 위치가 지났다면 멈춘다.
4) b의 위치에 적혀 있는 값을 출력한다.
import java.util.Scanner;
public class DutyTeacher97 {
// 선생님과 누군가의 위치
public static int a, b;
// 3가지 능력
public static int[] p= new int[3];
// 위치까지 몇번만에 올 수 있는지 나타내는 배열
public static int[] dt = new int[1001];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
for (int i = 0; i < 3; i++)
p[i]=sc.nextInt();
sc.close();
// 배열을 -1로 초기화
for (int i = 0; i <=1000; i++)
dt[i]=-1;
// 선생님의 현재 위치는 0번만에 갈 수 있음
dt[a]=0;
// 3가지 능력에 대해 선생님 위치부터 확인해 감
for (int i=0; i<3; i++){
int cur=a;
// 누군가의 위치를 넘으면 그만 함
while (cur <=b){
// 현재 위치에서 해당 능력을 이용하면 갈 수 있는 위치가 -1이면 무조건 업데이트 현재 위치값 +1이 더 작으면 그값으로 업데이트
if (dt[cur+p[i]]==-1 || dt[cur+p[i]]>dt[cur]+1 ){
dt[cur+p[i]]=dt[cur]+1;
}
// 능력 사용한 위치로 이동
cur+=p[i];
}
}
// 누군가의 위치 값을 출력
System.out.println(dt[b]);
return;
}
}
Big O(n): n은 a와 b사이 거리 * 3개의 능력
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/DutyTeacher97.java