[Do It! 코딩테스트 자바편(김종관)] 문제 060(백준 1219번)

느낀점

• 코드 이해하는 데 급급한 문제
• else if (maxIncome[s] == Long.MAX_VALUE) maxIncome[e] = Long.MAX_VALUE; 부분이 약간 이해되지 않는다. 이 부분이 없어도 maxIncome[s]가 Long.MAX_VALUE라면 else if (maxIncome[e] < maxIncome[s] + incomeOfCity[e] - fee)에 걸려서 maxIncome[e] = = Long.MAX_VALUE;되는게 아닌가?
  • 아마 오버플로우의 문제아닐까? maxIncome[s]가 Long.MAX_VALUE라면 maxIncome[s] + incomeOfCity[e] - fee가 오버플로우될 수 있음. 그럼 다시 음수부터 시작하므로 else if문에 안 걸릴 수 있음
  • System.out.println(Long.MAX_VALUE + 1);로 출력해보니 확실히 오버플로우된 걸 알 수 있었음. 단순히 long형 변수에 범위 최댓값 넘는 값을 담을 때뿐만 아니라, 그냥 연산하고 출력할 때도 오버플로우된다고 유추할 수 있지 않을까?

문제

오민식의 고민 (백준: 1219번)

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int cityCnt, start, end, tranportCnt;
    static int[] incomeOfCity;
    static Edge[] edgeList;
    static long[] maxIncome;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        cityCnt = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        tranportCnt = Integer.parseInt(st.nextToken());

        maxIncome = new long[cityCnt];
        Arrays.fill(maxIncome, Long.MIN_VALUE);

        edgeList = new Edge[tranportCnt];
        for (int i = 0; i < tranportCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int fee = Integer.parseInt(st.nextToken());
            edgeList[i] = new Edge(s, e, fee);
        }

        incomeOfCity = new int[cityCnt];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < cityCnt; i++) {
            incomeOfCity[i] = Integer.parseInt(st.nextToken());
        }

        // 알고리즘 수행
        maxIncome[start] = incomeOfCity[start];
        for (int i = 0; i < cityCnt + 100; i++) {
            for (int j = 0; j < tranportCnt; j++) {
                Edge now = edgeList[j];
                int s = now.s;
                int e = now.e;
                int fee = now.fee;

                if (maxIncome[s] == Long.MIN_VALUE)
                    continue;
                else if (maxIncome[s] == Long.MAX_VALUE)
                    maxIncome[e] = Long.MAX_VALUE;
                else if (maxIncome[e] < maxIncome[s] + incomeOfCity[e] - fee) {
                    maxIncome[e] = maxIncome[s] + incomeOfCity[e] - fee;

                    if (i >= cityCnt - 1)
                        maxIncome[e] = Long.MAX_VALUE;
                }
            }
        }

        if (maxIncome[end] == Long.MIN_VALUE)
            System.out.println("gg");
        else if (maxIncome[end] == Long.MAX_VALUE)
            System.out.println("Gee");
        else
            System.out.println(maxIncome[end]);
    }
}

class Edge {
    int s;
    int e;
    int fee;

    public Edge(int s, int e, int fee) {
        this.s = s;
        this.e = e;
        this.fee = fee;
    }

}