2. 시뮬레이션

 

안녕하세요, ICMP입니다.

이번 포스팅에서는 전체 탐색을 이용한 문제 풀이를 진행할 것입니다.

 

프로그래밍 실력을 늘리는 방법은 직접 프로그램을 개발해보거나 다양한 문제를 직접 풀어 봄으로서 상황을 논리적으로

분리시키는 능력을 키워야 합니다.

 

아직까지 저는 코딩에 익숙하지 않아 백준이나 정올 알고리즘 문제가 너무 어려웠습니다.

마치 일반 교재의 문제와 알고리즘 문제 간의 커다란 벽이 있는 느낌이었습니다.

 

TopCodder에 수록된 문제 일부를 선정하여 코딩을 공부하는 학생들의 고역을 조금이나마 줄이고자

포스팅을 진행합니다.

 

시작하기에 앞서, 문제 풀이에 사용될 주 언어는 C++입니다.

자, 그럼 오늘의 문제인 KiwiJuiceEasy를 풀어보도록 하겠습니다.

 

 

 

문제(Problem Statement)

 

Taro has prepared delicious kiwi fruit juice. He poured it into N bottles numbered from 0 to N-1. The capacity of the i-th bottle is capacities[i] liters, and he poured bottles[i] liters of kiwi juice into this bottle.

(타로는 맛있는 키위 과일 주스를 준비했다. 그는 그것을 0부터 N-1까지 번호가 매겨진 N 개의 병들에 부었다. i 번째 병의 용량은capacities[i] 리터이고, 그는 그 병에bottles[i] 리터의 키위 주스를 부었다)

 

Now he wants to redistribute juice in the bottles. In order to do this, he will perform M operations numbered from 0 to M-1 in the order in which he will perform them. For the i-th operation, he will pour kiwi juice from bottle fromId[i] to bottle toId[i]. He will stop pouring when bottle fromId[i] becomes empty or bottle toId[i] becomes full, whichever happens earlier.

(이제 그는 병에 든 주스를 재분배하고 싶어 한다. 이를 위해, 0부터 M-1까지 번호가 매겨진 M 번의 연산을 수행하게 된다. i 번째 연산에 대하여,fromId[i] 병에서toId[i] 병으로 키위 주스를 붓는다. 그는fromId[i] 병이 비거나toId[i] 병이 가득 차면 붓기를 멈추게 된다.)

 

Return an that contains exactly N elements and whose i-th element is the amount of kiwi juice in the i-th bottle after all pouring operations are finished.

(모든 붇기 작업이 완료된 후, 정확히 N 요소가 들어 있고 i 번째 요소가 i 번째 병에 들어 있는 키위 주스의 양인 것을 반환한다.)

- 다시 말해 존재하는 모든 병 개수와 각각의 병의 현재 키위 주스 양을 배열로 저장, 반환해야 한다는 것입니다.

 

 

 

정의(Definition)

Class: KiwiJuiceEasy (클래스 이름)

Method: thePouring (메소드 이름)

Parameters: int[], int[], int[], int[] (피라미터 - 인자)

Returns: int[] (반환 형)

Method signature: int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId) (함수의 정의 부분)

(be sure your method is public) (접근 제어문)

 

제한(Limits) -- 지금은 코딩을 연습하는 단계이니 이 부분은 과정상 생략합니다!!!

Time limit (s): 840.000

Memory limit (MB): 64

 

 

 

제약 (Constraints)

 

- capacities will contain between 2 and 50 elements, inclusive.

(capacities 요소는 2~50 개를 가집니다.)

 

- Each element of capacities will be between 1 and 1,000,000, inclusive.

(capacities 각각의 원소는 1~1000000 사이의 값을 가집니다.)

 

- capacities and bottles will contain the same number of elements.

(capacities과 bottles은 서로 같은 원소 개수를 가집니다.)

 

- For each i, bottles[i] will be between 0 and capacities[i], inclusive.

(각각의 i에 대하여, bottles[i]는 0~capacities[i] 사이의 값을 가집니다.)

 

- fromId will contain between 1 and 50 elements, inclusive.

(fromId의 원소는 1~50사이의 개수를 포함합니다.)

 

- fromId and toId will contain the same number of elements.

(fromId와 toId는 서로 같은 원소 개수를 가집니다.)

 

- Each element of fromId and toId will be between 0 and N-1, inclusive, where N is the number of elements in capacities.

(fromId와 toId의 각각의 요소는 capacities의 원소 개수인 N에 대하여 0~N-1을 인덱스로 가집니다. )

 

- For each i, fromId[i] and toId[i] will be distinct.

(각각의 i에 대하여, fromId[i]와 toId[i]는 서로 다른 값을 가집니다.)

 

 

Examples(테스트 예제)

 

{20, 20}

{5, 8}

{0}

{1}

Returns: {0, 13 }

He pours kiwi juice from bottle 0 to bottle 1. After pouring, bottle 0 will become empty and bottle 1 will contain 13 liters of kiwi juice.

 

{10, 10}

{5, 8}

{0}

{1}

Returns: {3, 10 }

He will stop pouring when bottle 1 becomes full.

 

{30, 20, 10}

{10, 5, 5}

{0, 1, 2}

{1, 2, 0}

Returns: {10, 10, 0 }

 

{14, 35, 86, 58, 25, 62}

{6, 34, 27, 38, 9, 60}

{1, 2, 4, 5, 3, 3, 1, 0}

{0, 1, 2, 4, 2, 5, 3, 1}

Returns: {0, 14, 65, 35, 25, 35 }

 

{700000, 800000, 900000, 1000000}

{478478, 478478, 478478, 478478}

{2, 3, 2, 0, 1}

{0, 1, 1, 3, 2}

Returns: {0, 156956, 900000, 856956 }

 

 

 

문제 분석

 

1. 상황 이해하기( capacities, bottles, fromId, toId 배열의 역할 이해)

각각의 병 용량을 capacities 배열에, 병에 담긴 주스량을 bottles, 옮길 주스 위치에 대한 배열 fromId, toId가 존재합니다.

처음에는 병의 용량과 담긴 주스량을 배열에 저장합니다.

그리고 주스를 옮길 병의 위치에 대한 주소를 배열로 저장하고, 배열 fromId과 toId을 통해 주스를 이동시킵니다.

모든 연산이 끝나면 현재 병에 들어있는 주스량을 저장한 배열 bottles을 함수 결과로 리턴합니다.

 

 

2. 발생할 상황 분기 예측

문제에서는 "fromId[i] 병에서toId[i] 병으로 키위 주스를 붓는다."라고 서술되어 있습니다.

그렇다면 주스를 옮기는 상황에 대한 분기를 생각해 봅시다.

capacities[toId[i]] - bottles[toId[i]]를 주스 담을 병의 여유 공간이라고 하면 다음과 같이 분기가 존재합니다.

 

첫 번째 :capacities[toId[i]] - bottles[toId[i]] > bottles[fromId[i]]

두 번째 :capacities[toId[i]] - bottles[toId[i]] = bottles[fromId[i]]

세 번째 :capacities[toId[i]] - bottles[toId[i]] < bottles[fromId[i]]

 

첫 번째, 두 번째 경우

주스를 부을 병의 여유 공간이 옮겨지는 주스 양보다 크거나 같으므로 다음과 같이 처리하면 됩니다.

bottles[toId[i]] = bottles[toId[i]] + bottles[fromId[i]]

bottles[fromId[i]] = 0

 

세 번째 경우

주스를 부을 병의 여유 공간이 옮겨지는 주스 양보다 작으므로 다음과 같이 처리하면 됩니다.

bottles[toId[i]] = capacities[toId[i]]

bottles[fromId[i]] = bottles[fromId[i]] - (capacities[toId[i]] - bottles[toId[i]])

 

 

 

위에서 서술한 내용을 그림으로 표현하면 다음과 같습니다.

(순서도 규칙을 준수하여 작성한 것이 아닙니다.)

 

 

 

3. 조건에 맞추어 클래스를 작성

 

문제 조건에서 다음과 같이 명시되어 있습니다.

Class Name : KiwiJuiceEasy Method Name : thePouring Return Type : int[]Arg Types : (int[], int[], int[], int[])

포인터를 배운 들이라면 함수에 배열 시작 주소만 가리키는 것만 가능하고 배열의 크기를 따로 함수에 전달해야 한다고 들었을 겁니다. 그런데 함수 인자가 (int[], int[], int[], int[]) 4개 뿐이므로 C++의 vector class를 이용하도록 하겠습니다.

 

 

#include <iostream>
#include <vector>
using namespace std;
 
class KiwiJuiceEasy {
public:
    vector <int> capacities;
    vector<int>bottles;
    vector<int>fromId;
    vector<int>toId;
 
    vector<int> thePouring(
        vector <int> capacities, vector<int>bottles, vector<int>fromId, vector<int>toId) {
 
        for (int i = 0; i < bottles.size(); i++) {
            int A = capacities[toId[i]] - bottles[toId[i]];
            int B = bottles[fromId[i]];
 
            if (A >= B) {
                bottles[toId[i]] = bottles[toId[i]] + bottles[fromId[i]];
                bottles[fromId[i]] = 0;
            }
 
            else {
                bottles[toId[i]] = capacities[toId[i]];
                bottles[fromId[i]] = bottles[fromId[i]] - (capacities[toId[i]] - bottles[toId[i]]);
            }
 
        }
        return bottles;
    }
 
};
 
 

 

 

또한 아래 링크를 통해 지금까지 가장 정확한 코드와 자신이 작성한 코드를 비교하며 어떤 부분이 다른지 공부하시면 좋을 듯합니다. C++ 말고 다른 언어도 있으니 참고하시길 바랍니다.

영어 해석은 오역이 많으므로 댓글로 피드백 부탁드립니다.

 

https://community.topcoder.com/tc?module=ProblemDetail&rd=14187&pm=11020

TopCoder Statistics - Problem Archive

 

이상, ICMP였습니다.

감사합니다!!!