[문제해결을 위한 창의적 알고리즘] 숙직 선생님 (고급 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

문제해결을 위한 창의적 알고리즘 목록