[문제해결을 위한 창의적 알고리즘] 잭과 콩나물 (고급 p.118)

이 문제는 3중 중첩 for문을 사용하여 문제를 해결하고 있다. 문제 설명이 좀 아쉬운 점은, 주어진 m개의 가로 콩나물 외에 가로 콩나물을 더 추가할 수 있는데 주어진 2개의 콩나물 사이에 얼마든지 추가할 수 있다는 점이다. 즉, m개의 가로 콩나물이 1의 간격으로 주어지지만 추가하는 콩나물은 1 간격 사이에 얼마든지 추가할 수 있다.

비슷한 형태로 Floyd-Warshall (all pairs shortest path) 알고리즘도 참고해 보면 좋을 것 같다.

import java.util.Scanner;

public class JackAndBeanStalkSol123 {

public static int n, m;

public static int[] p=new int[501];

public static int[][] DT=new int[501][101];

public static boolean isIn(int a, int b, int k){

return ((a<=k && k < b) || (b<=k && k < a)) ? true : false;

}

public static int abs(int a){

return a > 0? a : -a;

}

public static void main(String[] args){

int a, b, X, Y;

int i, j, k;

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

m = sc.nextInt();

a = sc.nextInt();

b = sc.nextInt();

X = sc.nextInt();

Y = sc.nextInt();

for (i=1; i <=m; i++)

p[i]=sc.nextInt();

// 임의의 무한대 값으로 설정

for (i=0; i<=m; i++)

for (j=0; j<=n; j++)

DT[i][j]=99999999;

// 0번째 줄에서 j번째 줄까지 가기 위해 필요한 콩나물 추가 비용으로 초기화

for (j=1; j<=n; j++)

DT[0][j]=abs(j-a)*Y;

for (i =1; i <=m; i++)

for (j=1; j<=n; j++)

for (k=1; k<=n; k++)

// m번째 가로줄까지 왔을때, 현재 위치가 j번째 세로 콩나물 위치와 같고, 가로 콩나물 선으로 연결되어 있다면, 직전 위치에서 가로 콩나물선을 제거하는 비용과 그냥 두는 비용 중 작은 것 선택

if (j==k && (p[i]==k || p[i]+1==k))

DT[i][j] = (DT[i-1][k]+X < DT[i][j])?DT[i-1][k]+X:DT[i][j];

// 만약 현재 위치와 j번째 세로 콩나물 사이에 가로 콩나물이 연결되어 있으면 (1개 있을 수 있음), 둘 사이를 연결할 수 있는 개수 만큼 가로 콩나물 추가 

else if (isIn(j,k,p[i]))

DT[i][j]=DT[i-1][k]+(abs(j-k)-1)*Y < DT[i][j] ? 

DT[i-1][k]+(abs(j-k)-1)*Y:DT[i][j];

// 만약 현재 위치와 j번째 세로 콩나물 사이에 가로 콩나물이 연결되어 있지 않으면 둘 사이를 연결할 수 있는 개수 만큼 가로 콩나물 추가

else

DT[i][j] = DT[i-1][k]+abs(j-k)*Y < DT[i][j]?

DT[i-1][k]+abs(j-k)*Y:DT[i][j];

System.out.println(DT[m][b]);

}

}

Big O(n^2*m)

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/JackAndBeanStalkSol123.java

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