[SW Expert Academy] 1850번 - 백만장자 프로젝트 문제

많이 바빴어서 그동안 알고리즘 문제를 거의 풀지 못하고 지냈다.

졸업하고 올 초에 얼마간 휴식기를 가진 뒤 바로 정처기 준비를 했다.

자격증도 좋지만 내게 지금 가장 필요한 공부는 알고리즘, 코테 준비인 것 같으므로 다시 마음을 가다듬고 잘 공부해보려 한다.

문제는 백준 + sw expert academy에 있는 문제들 위주로 풀어보려 한다.

 

swexpert에서 문제를 난이도별로, 추천순으로 풀어보고자 처음으로 선택한 문제다.

문제는 이러하다.

 

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

[예제 풀이]
1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.
2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

난이도는 d2로 되어 있지만 푸는데 꽤나 오래 걸렸다.

뒤에 더 매매가가 높은 날이 있다면 그보다 앞선 날들에서 물건들 다 사들이고 그날 판매해서 이득을 본다.

그리고 매매가가 높은 날이 뒤에 또 있다면 마찬가지로 앞선 날들에서 물건을 매입하고 그날 판매해서 이득을 본다.

매매가가 가장 높은 날 최대한 파는것이 이득이므로 우선 N일 중 언제가 가장 매매가가 높은지를 파악해야한다.

그리고 그 다음에 오는 날들 중 언제가 가장 매매가가 높은지를 마찬가지로 확인해 매매한다.

각 날의 매매가를 표시하는 배열을 만들어 최고 매매가를 찾아 최대이득을 계산하고, 배열의 그 다음부터 다시 탐색 - 계산 과정을 거쳐가며 

마지막까지 얻을 수 있는 최대 이익을 계산을 하면 되겠다고 생각했다.

처음에는 배열 전체를 탐색하겠지만, 반복할수록 탐색 범위가 줄어드는 식이다.

간만에 문제를 풀어서 그런가 조건식도 이상하게 쓰고 for문 때문에 무한 루프도 돌아보고

이것저것 실수를 많이 하는 바람에 풀이 시간이 더 늦어진 것 같다.

반복문의 경우 몇번 반복시킬지 미리 확실히 알 수 없으므로 while문으로 쓰면 적합했을 것을 for문으로 했다가

쓸데없이 고민도 많이 했고 이런저런 실수들 때문에 고치느라 시간 많이 썼다..!

문제 많이 풀어보면서 앞으론 더 잘풀어야지!!

 

더 효율적인 방법이 있겠지만, 나 나름대로 열심히 풀어본 코드는 이러하다.

package D2;

import java.io.*;
import java.util.StringTokenizer;

public class SW_1859 {  //백만장자 프로젝트 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());    //테스트 케이스의 수 입력받기

        int N;
        int max;    //입력받을 값들 중 가장 큰 값, 갱신됨
        int maxIndex;   //  max의 위치
        int profit; //얻을수있는 총 이득
        int sum;    //max값 앞에 위치한 값들의 합
        int sumCount;   //max값 앞에 위치한 값들의 개수
        int temp;
        int prevMaxIndex;

        for (int i = 0; i < T; i++) {
            //반복할때마다 이것들은 초기화해줘!!
            profit = 0;  temp = 0; prevMaxIndex = -1; maxIndex = 0;

            //입력받은 값들 배열에 저장
            N = Integer.parseInt(br.readLine());    //입력받을 자연수의 개수, 배열의 크기 결정
            int[] str = new int[N];    //크기 N의 정수형 배열 생성
            StringTokenizer st = new StringTokenizer(br.readLine());    //띄어쓰기(공백)기준으로 문자열 분리
            for (int j = 0; j < N; j++) {   //배열에 차례대로 정수 입력받기
                str[j] = Integer.parseInt(st.nextToken());
            }

            //maxIndex값은 배열 내의 수들 중 가장 큰 수의 index를 의미한다
            //한번 max값이 정해지고 나면, 그 다음 반복이 될 때는 배열 0번째부터 해당 maxIndex값까지는 제외하고 탐색하도록 한다.
            //따라서 profit 계산이 끝나고 나면 maxIndex값을 하나 증가시켜 그 다음부터 배열 끝까지 탐색되도록 한다.
            //조건식좀 잘 보자!!!
            while (maxIndex <= N - 1) { //maxIndex값이 배열의 가장 마지막 인덱스 값이 될때까지 반복
                sum = 0; sumCount = 0; max = 0;   //한번 돌때마다 0으로 초기화해주어야 하는 녀석들
                temp = maxIndex;
                while (temp < N) {  //몇번 반복되어야 할지 불명확한 경우니까 while문을 사용
                    if (str[temp] >= max) {
                        max = str[temp];
                        maxIndex = temp;
                    }
                    temp++; //밑에서 maxIndex값을 사용해야 하므로 temp에 따로 저장하여 temp가 증가되며 배열 끝까지 돌도록 한다
                }

                temp = prevMaxIndex + 1; //이전의 maxIndex값 다음에 오는 Index값을 cnt에 저장, 여기서부터 출발해서 더해나가야 함
                while (temp < maxIndex) {
                    sum += str[temp];
                    sumCount++;
                    temp++;
                }
                //이전 maxIndex값 다음에 오는 값(preMaxIndex + 1)에서부터 현 maxIndex 이전까지의 값들의 개수롤 max와 곱하고,
                // 곱한 값에서 그 이전까지의 값들의 총합을 뺴면 여기까지 얻을수있는 최대 이득이 계산된다
                profit += max * sumCount - sum;
                prevMaxIndex = maxIndex;
                maxIndex++; //여기서 값 증가시켰으므로 다음 반복이 될때 여기서 출발해서 max값을 찾으면 된다

            }

            bw.write("#" + (i + 1) + " " + Integer.toString(profit));  //다시 String으로 바꾸는거 잊지말기
            bw.newLine();   //줄바꿈!
        }
        bw.flush(); //비우기
        bw.close(); //닫기






    }
}

 

다음과 같이 코드를 제출하니 테스트케이스 10개중 7개만 맞아 오답 처리되었다.

뭔가 빠트린 부분이 있는 모양이다

이 문제에 들인 시간이 꽤 돼서 더이상 끙끙 고민하는건 조금 시간낭비일 것 같아

밑에 달린 댓글을 참고해서 수정하기로 했다

문제 밑에 달린 다음의 댓글들을 참고하여 수정했다

 

 Java로 푸시는 분들 10개 중 7개만 맞으면 int범위를 넘어가서 그런겁니다. 100만개가 넘다보니 20억을 넘네요.

올 수 있는 출력 값이 대략 1,000,000(N) * 10,000(매매가)이 될 수 있다는 걸 고려해야 합니다;;

 

따라서 profit 변수의 자료형을 long형으로 바꿔주었다(출력되는 부분도 함께 변경해주었다)

int범위를 벗어날만한 값을 가질 변수는 profit 하나뿐이라 해당 변수만 long형으로 변경했는데,

어째서인지 여전히 7개 테스트 케이스만 통과되었다고 떠서 댓글을 좀더 찾아보았다.

그러다나 (내 기준) 놀라운 사실을 알게 되었다..

 

long long형 변수 = long long형 변수 + int형 변수*int형 변수 로 할때, 'int형 변수*int형 변수'의 계산값이 표현할 수 있는 범위는 int의 표현범위와 같기 때문에 실제 곱한 값이 int 범위 밖이면 우리가 원하던 값이 아니게 됩니다. 전 알고리즘은 맞았는데 이 부분을 고려하지 못해서 10개중 7개의 테스트 케이스만 맞더라고요. 어디서 틀렸는지 고민하는데 꽤 오래 걸렸어서 혹시 저랑 비슷한 상황에 처하신분들 있으면 도움이 됬으면 하네요 ㅎㅎ

 

어떠한 형 범위의 결과값을 얻기 위해서는 해당 계산에 쓰이는 피연산자들의 형도 마찬가지어야 하는구나..

그래서 profit 뿐만 아니라 profit 계산에 쓰이는 모든 변수들의 형을 long으로 바꿔주었고,

그러니까 Pass가 떴다.휴..

 

 

 

댓글을 살펴보니 배열 뒤에서부터 보는 방법으로 푸는 방식이 있다고 한다. 나는 그렇게 풀진 않았지만

그 방법이 궁금해서 다른 사람의 코드를 살펴보았다.

아 대박..

핵심 코드 부분만 가져와보았다

for (int j = n-1; j >=0; j--) {
	if(arr[j]>max_value)max_value=arr[j]; 
    diff+=max_value-arr[j]; 
}

진심 간단명료하다

배열 뒤에서부터 시작하여 max값을 갱신하며 하나씩 하나씩 이득을 계산해나가는 그런 식인거다

나는 앞에서부터 시작하는 방법으로 해서 불필요하게 코드가 복잡해졌구나 싶다

단순하지만 나는 풀때 전혀 생각하지 못했던 방법..이렇게 또 하나 느끼고 간다!