시뮬레이션은 프로그래밍 대회에서 가장 쉬운 문제이며 초기 상태와 어떤 작업을 수행할지 제공하고 최종 결과가 어떻게 될지 답하는 문제이다. 이런 문제는 무엇을 해야할 지 문제에 모두 쓰여있다.
4-1. 키위 주스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
타로는 맛있는 키위 주스를 준비했습니다. 타로는 0부터 N-1이라는 이름을 붙인 N개의 병에 키위주스를 넣었습니다. 이때 i번째의 병의 용량은 capacities[i] 리터이며 타로가 i번째 병에 넣은 키위 주스의 양을 bottles[i] 리터라고 합니다.
타로는 병에 키위 주스를 재분배하려고 하며, 0부터 M-1까지 M회 조작합니다. i번째의 조작은 타로가 병 fromId[i]부터 병 toId[i]에 키위 주스를 넣는 것을 의미합니다.
병 fromId[i]가 비어있거나 병 toId[i]가 꽉 차 있는 순간, 타로는 더이상 키위 주스를 넣지 않습니다.
N개의 요소를 가진 정수 배열 int[]를 리턴해주세요. 배열의 i번째 요소는 모든 주스를 쏟는 작업이 완료되고 i번째 병에 남아 있는 키위 주스의 양입니다.
[클래스와 함수 정의]
Class : KiwiJuiceEasy
method : public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId)
[제약조건]
* capacities : 2~50개의 요소가 있는 배열이고, 각 요소는 1~1000000 사이의 값을 갖는다.
* bottles : capacities와 같은 수의 요소가 있는 배열이고 bottles[i]는 capacities[i]에 들어있는 주스를 의미한다.
* fromId : 1~50개의 요소가 있는 배열이다.
* toId : fromId와 같은 수의 요소가 있는 배열이다.
변수 fromId와 toId는 0~(N-1) 사이의 값이다. 이때 N은 변수 capacities의 항목 개수이다. fromId[i]와 toId[i]는 서로 다른 값을 갖는다.
나의 답
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package ex1;
public class KiwiJuiceEasy {
public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
for (int i = 0; i < fromId.length; i++) {
//키위 주스를 옮긴다
bottles[toId[i]] += bottles[fromId[i]];
//옮긴 주스가 병의 용량보다 많다면 용량만큼 담는다.
if(bottles[toId[i]] > capacities[toId[i]]) {
bottles[fromId[i]] = bottles[toId[i]] - capacities[toId[i]];
bottles[toId[i]] = capacities[toId[i]];
}else {
bottles[fromId[i]] = 0;
}
}
return bottles;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import ex1.KiwiJuiceEasy;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
//0. 결과 [0, 13]
int[] capacities = {20, 20};
int[] bottles = {5, 8};
int[] fromId = {0};
int[] toId = {1};
//1. 결과 [3, 10]
capacities = new int[]{10,10};
bottles = new int[]{5, 8};
fromId = new int[]{0};
toId = new int[]{1};
//2. 결과 [10, 10, 0]
capacities = new int[]{30, 20,10};
bottles = new int[]{10, 5, 5};
fromId = new int[]{0, 1, 2};
toId = new int[]{1, 2, 0};
//3. 결과 [0, 14, 65, 35, 25, 35]
capacities = new int[]{14, 35, 86, 58, 25, 62};
bottles = new int[]{6, 34, 27, 38, 9, 60};
fromId = new int[]{1,2,4,5,3,3,1,0};
toId = new int[]{0,1,2,4,2,5,3,1};
//4. 결과 [0, 156956, 900000, 856956]
capacities = new int[]{700000, 800000, 900000, 1000000};
bottles = new int[]{478478, 478478, 478478, 478478};
fromId = new int[]{2,3,2,0,1};
toId = new int[]{0,1,1,3,2};
KiwiJuiceEasy kiwiJuiceEasy = new KiwiJuiceEasy();
int[] returns = kiwiJuiceEasy.thePouring(capacities, bottles, fromId, toId);
System.out.println(Arrays.toString(returns));
}
}
문제 해설
예시 0, 1을 보면 주스를 옮기는 작업은 두 가지로 구분된다.
- 주스를 모두 옮겼는데 넘치지 않고 전부 들어간 경우 :
옮길 주스의 양 <= 기존 주스 병의 남은 용량(모든 주스를 옮길 수 있다.) - 주스를 모두 옮겼는데 넘쳐버린 경우 :
옮길 주스의 양 > 기존 주스 병의 남은 용량(옮길 주스의 양은 기존 주스 병의 남은 용령 만큼이다.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class KiwiJuiceEasy {
public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
for (int i = 0; i < fromId.length; i++) {
int f = fromId[i];
int t = toId[i];
int space = capacities[t] - bottles[t]; //기존 주스병의 남은 용량
//옮길 주스의 양 <= 기존 주스 병의 남은 용량
if(bottles[f] <= space) {
int vol = bottles[f];
bottles[t] += vol;
bottles[f] = 0;
//옮길 주스의 양 > 기존 주스 병의 남은 용량
} else {
int vol = space;
bottles[t] += vol;
bottles[f] -= vol;
}
}
return bottles;
}
}
응용기술 1 - 조건문을 조금만 사용하기
if문 대신 min, Math.min 등의 최솟값 함수를 사용하여 코드를 간단히 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class KiwiJuiceEasy {
public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
for (int i = 0; i < fromId.length; i++) {
int f = fromId[i];
int t = toId[i];
//옮길 주스의 양과 기존 주스 병의 남은 용량 중 적은 값을 가져온다.
int vol = Math.min(bottles[f], capacities[t] - bottles[t]);
bottles[f] -= vol;
bottles[t] += vol;
}
return bottles;
}
}
응용기술 2
필자는 이동량을 무시하고 옮길 주스와 기존 주스의 양의 총합이 일정하다는 것과 옮길 주스는 주스 총량과 기존 주스 병의 용량 중에 작은 값이 된다는 것을 이용하기로 했다.
- 기존 주스 : 옮길 주스와 기존 주스의 총합, 기존 주스 병의 용량 중 작은 값
- 옮길 주스 : 옮길 주스와 기존 주스의 총합에서 위의 값을 제외한 값
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class KiwiJuiceEasy {
public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
for (int i = 0; i < fromId.length; i++) {
//옮길 주스와 기존 주스의 총합
int sum = bottles[fromId[i]] + bottles[toId[i]];
//옮길 주스와 기존 주스의 총합, 기존 주스 병의 용량 중 작은 값
bottles[toId[i]] = Math.min(sum, capacities[toId[i]]);
//옮길 주스와 기존 주스의 총합에서 위의 값을 제외한 값
bottles[fromId[i]] = sum - bottles[toId[i]];
}
return bottles;
}
}
정리
- 문제를 이해했다면 손으로 계산하라
- 코딩이 오래 걸린다면 다시 한 번 손으로 생각하라
- 조건문은 되도록 조금 사용하라