[코드트리] 용량이 다른 3개의 물통 (시뮬레이션) - JAVA

알고리즘 스터디 - Simulation

https://www.codetree.ai/training-field/search/problems/three-water-bottles-with-different-capacities/description?page=1&pageSize=20&tags=Backtracking%2CSimulation&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

# 문제

 

 

# 예제

입력

10 3
11 4
12 5

 

출력

0
10
2

 

 

# 필요개념

물을 다른 병에 옮길 때 생각해야 하는 포인트는 두 가지라고 생각했다.

• 병의 용량을 초과하는 경우 -> 병을 꽉 채우고, 못 넣은 물은 기존 물병에 남는다.
• 병의 용량을 초과하지 않는 경우 -> 옮길 물병의 물 양이 바뀐다.

 

물을 100번 옮겨야 하기 때문에, 이를 메소드로 만들고 위 두가지 부분을 반영하였다.

 

 

# Code

import java.util.*;
import java.io.*;
public class Main {
    static List<Bottle> lst = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0 ; i < 3 ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lst.add(new Bottle(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        for (int i = 0 ; i < 100 ; i++) {
            moveWater(i % 3);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(lst.get(0).rest).append("\n").append(lst.get(1).rest).append("\n").append(lst.get(2).rest);
        System.out.println(sb.toString());
    }

    public static void moveWater(int i) { // i = 0, 1, 2
        int bottle1 = lst.get(i).getRest();
        int bottle2 = lst.get((i + 1) % 3).getRest();

        if (lst.get((i + 1) % 3).getMaximum() >= bottle1 + bottle2) {
            lst.get((i + 1) % 3).setRest( bottle1 + bottle2);
            lst.get(i).setRest(0);
        }
        else {
            lst.get((i + 1) % 3).setRest(lst.get((i + 1) % 3).getMaximum());
            lst.get(i).setRest(bottle1 + bottle2 - lst.get((i + 1) % 3).getMaximum());
        }
    }

    static class Bottle {
        private int maximum;
        private int rest;
        public Bottle(int maximum, int rest) {
            this.maximum = maximum;
            this.rest = rest;
        }

        public void setRest(int rest) {
            this.rest = rest;
        }

        public int getMaximum() {
            return maximum;
        }

        public int getRest() {
            return rest;
        }
    }
}

 

#결과