시뮬레이션 문제

시뮬레이션 문제란?

알고리즘을 풀 때 모든 과정이 제시되어 그 과정을 거쳐 나온 결과를 추론하는 문제입니다.

시뮬레이션은 설명해 준 대로 쭉 이행하면 됩니다.

코드에서 간단하게 설명드리도록 하겠습니다.

문제

( i 번째 기준 )

병의 용량 : capacities[i];

주스의 양 : bottles[i];

주스를 붓는 양 : toId[i];

주스를 붓고 남은 양 : fromId[i];

문제는 빈 병에다가 주스를 재분배해서 담으려하는데 0부터 M-1번째까지 M회 조작합니다.

i 번째 조작에 있어서는 fromId[i]부터 toId[i]에 주스를 담는 것을 의미합니다.

병 fromId[i]가 비어 있거나 병 toId[i]가 꽉 차 있다면 더이상 주스를 분배할 수 없습니다.

이러한 문제는 시키는 대로 순서대로 하면 되는데, 우선 이해해봅시다.

i번째 병에서 주스를 다른 병에 분배할 때 

fromId[i] 만큼 부으면 그 만큼 toId[i]에 채워지게 됩니다.

즉, bottles[fromId[i]] 만큼 부으면 bottles[toId[i]]는 그 만큼 채워지기 마련입니다.

단, bottles[toId[i]]는 bottles[fromId[i]] 만큼 채워지되, capacities[i] 보다 작아야 합니다. 

for(int i=0;i<fromId.length;i++){

int f = fromId[i]; // f 만큼 붓는 것

int t = toId[i]; // t 만큼 채워지는 것

int space = capacities[t] - bottles[t]; // t만큼 채워질 때 그 때의 병 용량 비는것과 채워지는 양만큼 계산했을 때 더 담을 수 있는 공간을 의미함.

if(space >= bottles[f]) {  // f 만큼 부을 때의 주스 양 >> 이것 보다는 담을 수 있는 공간이 더 커야함(같아도 됨)

int vol = bottles[f]; // f 만큼 부을 때의 주스 양

bottles[t] += vol;    // 부은 만큼 채워져야함

bottles[f] = 0;        // 가득 찰 경우 (붓는 만큼의 양을 딱 맞춰서 채워질 경우)

} else {

int vol = space;     // 여유 공간이 더 작기 때문에 여유 공간 만큼만 채워야함

bottles[t] += vol;   // 부은 만큼 채워져야함

bottles[f] -= vol;    // 여유 공간만큼 부었기 때문에 남을 것임 부어야 할 만큼에서 부은 만큼 빼서 남을 것을 계산

}

}

이런 식으로 정리할 수 있습니다.

추가로 조금 더 심화하자면 조건문으로 나눈 기준이 결국 여유 공간을 가지고 계산한 것이기 때문에 이를 수학적 사고를 가지고 변형할 수 있습니다.

i 번째의 병에서 주스를 부을 양과 담을 양을 계산해서 더해주면 결국 부어야할 전체의 양이 나오게 됩니다.

주스를 부어야 할 전체의 양에서 전체 병의 용량과 비교했을 때, 더 작은 값을 가지고 부어질 양에서 빼주면 됩니다.

public static int[] pour_the_juice(int[] capacities, int[] bottles, int[] fromId, int[] toId) {

/*

* 부을 수 있는 양 : fromId[i]; 붓는 양 : toId[i]; 전체 주스 양 : bottles[i]; 담겨질 수 있는 병의 용량 :

* capacities[i];

*/

/*

* 구조 1. 주스에서 붓는 양 만큼 해서 부을 경우 가득 채워질 때 (전체 주스를 부을 양보다 병의 용량이 더 클 경우) 

* 구조 2. 주스에서 붓는 양 만큼 해서 부을 경우 다 담지 못할 때 (전체 주스를 부을 양보다 병의 용량이 더 작을 경우)

*/

for (int i = 0; i < fromId.length; i++) {

// 붓는 양과 부을 수 있는 양의 합계는 전체 부어야 할 주스의 양과 같음

int sum = bottles[fromId[i]] + bottles[toId[i]];

// 전체 부어야 할 주스의 양과 담겨질 수 있는 병의 용량을 비교한다.

// 비교할 때 구조1로 들어가는 지 구조2로 들어가는 지 확인한다. 이를 조건문으로 나눌 수 있지만

// 결국 전체 부어야 할 주스의 양과 담겨질 수 있는 전체 병의 용량의 최소값을 찾는다면 더 편하다.

// 만일 부어야 할 주스의 양이 더 작은 값이라면 다음에는 부을 값이 없기 때문에 붓는 양은 0이 될 것이다.

// 반대로 병의 용량이 더 작은 값이라면 병의 용량을 가득 채워서 부어도 부어야할 주스가 남을 것이다. 이것이 붓는양의 값이 될 것이다.

bottles[toId[i]] = Math.min(sum,capacities[i]);

bottles[fromId[i]] = sum - bottles[toId[i]];  

}

return bottles;

}

다음과 같이 진행하게 되면 같은 값을 같게 될 것입니다.

이렇듯, 시뮬레이션 문제는 과정을 천천히 접근해서 풀면 됩니다.

다음에는 탐색 문제를 풀어보도록 하겠습니다. 

감사합니다.