백준 17939번: Gazzzua(Python/Java)

https://www.acmicpc.net/problem/17939

17939번: Gazzzua

 

 

 

접근

---

실제 가상화폐든, 그리디 알고리즘의 가상화폐든 이득을 얻는 방법은 간단하다. 저점에서 사고 고점에서 파는 것이다. 만고불변의 진리. 그렇다면 이 문제는 어떻게 해결해야 할까? 저점에서 사고 고점에서 팔면 되지!!

 

우선 현재 주어진 값들 중에서 높은 값이 어디 있는지 확인한다. 그 고점이 나오기 전까지는 무조건 매입한다. 왜냐? 해당 고점보다 낮으면 얼마나 사들었는지 무조건 이득이기 때문이다. 해당 고점이 나오면 매입한 모든 코인을 판다. 그럼 이제부터 다시 확인해보자. 코인을 판 칸의 다음 칸부터 마지막 값까지 가장 높은 값을 찾는다. 그 뒤 또 가장 높은 값이 나올 때까지 매입한 뒤, 가장 높은 값에서 판다. 이를 계속 반복한다. 이렇게 하면 절대 손해보지 않고 코인을 사고팔 수 있게 된다.

 

 

 

풀이

---

Python

coinNum = int(input())
board = list(map(int, (input()).split()))

sumNum = 0
result = 0
subResult = 0
maxNum = max(board)
for i in range(coinNum):
    if board[i] < maxNum:
        subResult += board[i]
        sumNum += 1
    else:
        result += (maxNum*sumNum - subResult)
        if i != (coinNum-1):
            maxNum = max(board[i+1:])
        sumNum = 0
        subResult = 0

print(result)

 

Java

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        
        int coinNum = Integer.parseInt(scan.nextLine());
        String[] firstLine = (scan.nextLine()).split(" ");
        Integer[] board = new Integer[coinNum];
        Integer[] sortedBoard = new Integer[coinNum];
        int maxNum = 0;
        for(int i = 0 ; i < coinNum ; i++){
            board[i] = Integer.parseInt(firstLine[i]);
            maxNum = Math.max(maxNum, board[i]);
        }
        int subNum = 0, result = 0, subResult = 0;
        for(int i = 0 ; i < coinNum ; i++){
            if(board[i] < maxNum){
                subResult += board[i];
                subNum++;
            }else{
                result += (maxNum*subNum - subResult);
                if(i != (coinNum-1)){
                    maxNum = 0;
                    for(int j = (i+1) ; j < coinNum ; j++){
                        maxNum = Math.max(maxNum, board[j]);
                    }
                }
                subNum = 0;
                subResult = 0;
            }
        }

        System.out.println(result);
    }

}

 

 

 

후기

---

물론 정답에는 큰 영향을 미치지 않았을 것이긴 하지만 실수가 있었던 문제. java로 해결할 때, 처음 배열 내에서 가장 큰 값을 찾을 시, 그냥 배열에 값을 넣는 과정에서 찾아주면 되는데 굳이 배열을 정렬하고 그 뒤에 가장 앞의 값을 꺼냈었다. 풀다 보니 '내가 무슨 멍청한 짓을...'하고 호다닥 수정했다.

 

중요한 것은 결과적으로는 같은 값을 도출하더라도 조금 더 연산이 적고, 조금 더 효율적인 코드를 작성하는 것!!