Greedy - 15748

문제 설명

1. 총 등산 거리 L, 휴식 지점 갯수 N, 1m 가는데 존이 걸리는 시간 rF, 1m 가는데 베시가 걸리는 시간 rB가 주어진다.
2. 다음 줄부터 각 휴식지점의 거리 xi와 풀의 맛 ci가 주어진다.
3. 최대로 얻을 수 있는 풀의 맛을 출력한다.

조건

1. 존에게 추월당하면 안된다.

문제 풀이

그리디 알고리즘(Greedy Algorithm)으로 푸는 문제이다.

그리디 알고리즘(Greedy Algorithm)이란?

각 단계에서 그 순간에 최적이라고 생각되는 선택을 반복하여 최종적인 해답에 도달하는 알고리즘 설계 기법이다.

탐욕 알고리즘으로도 불린다.

 

따라서 각 단계에서 최적의 선택을 할 것인데, 여기서는 뒤에서부터 탐색을 하였다.

문제의 예제 입력과 출력으로 설명을 해보겠다.

 

입력

10 2 4 3
7 2
8 1

출력

15

 

1. 최대 맛을 가지고 있는 위치(maxPosition)와 맛(maxTastiness)을 기록하는 변수를 0으로 초기화한다.
2. 첫 번째 탐색구간인 xi(8)의 위치와 ci(1)의 맛이 기록되어 있는 최대 맛(maxTastiness)보다 큰지 확인한다.
3. 크다면 최대 맛(maxTastiness) * (최대 맛 위치(maxPosition) - 탐색 구간 위치(xi))를 결과 값에 더해준다.
   여기서는 0 * (0 - 8)로 0이 나온다.(당연히 휴식지점을 지나 종점에 도달한 경우 휴식할 수 없다.)
4. 이후 두 번째 탐색구간인 xi(7)의 위치와 ci(2)의 맛이 기록되어 있는 최대 맛(maxTastiness)보다 큰지 확인한다.
5. 크다면 최대 맛(maxTastiness) * (최대 맛 위치(maxPosition) - 탐색 구간 위치(xi))를 결과 값에 더해준다.
   여기서는 1 * (8 - 7)로 1이 나온다.
6. 이후 휴식지점을 모두 돌았기 때문에 시작점으로 도착했다.
7. 시작점에 도착한 경우 맛(maxTastiness) * 최대 맛 위치(maxPosition)를 계산해서 결과 값에 더해준다.
   여기서는 2 * 7로 14가 나온다.
8. 결과값은 따라서 1 + 14로 15가 나온다.

위 과정은 역순 탐색을 이용한 그리디 알고리즘 기법이다.

코드 풀이

using System;
using System.Collections.Generic;
using System.Linq;

namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            //입력 처리
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int L = input[0]; //등산 길이
            int N = input[1]; //휴식 지점
            int rf = input[2]; //존의 미터당 이동 시간
            int rb = input[3]; //베시의 미터당 이동 시간
            List<int> xArray = new List<int>(); //휴식 지점의 목록
            List<int> cArray = new List<int>(); //각 휴식 지점의 풀의 갯수 목록
            for (int i = 0; i < N; i++)
            {
                int[] input2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                xArray.Add(input2[0]);
                cArray.Add(input2[1]);
            }
            long grassNum = 0;
            int maxPoint = L;
            int maxPointGrass = 0;
            for(int i = xArray.Count - 1; i >= 0; i--)
            {
                if(maxPointGrass < cArray[i])
                {
                    grassNum += (long)(maxPoint - xArray[i]) * maxPointGrass * (rf - rb);
                    maxPointGrass = cArray[i];
                    maxPoint = xArray[i];
                }
            }
            grassNum += (long)maxPoint * maxPointGrass * (rf - rb);
            Console.WriteLine(grassNum);
        }
    }
}

위에서 설명한 것을 그대로 코드로 바꾸었다.

특이한 점이라면 자료형을 long을 사용했다는 점이다.

 

이유는 최대 거리가 10^6, 속도도 10^6, 맛도 10^6의 범위까지 계산이 되어야한다.

따라서 극한의 예시로 휴식지점 xi가 10^6 - 1과 맛이 10^6, 존의 미터당 이동 시간 rf가 1이고 베시의 미터당 이동 시간 rb가 10^6, 으로 주어진다.

이 데이터의 출력값은 (10^6 - 1)(휴식 지점) * (10^6 - 1)(여유 시간) * 10^6(맛)으로 나온다.

따라서 10^18(1,000,000,000,000,000,000)까지 나오게 되므로 4바이트 크기의 int는 2^32(4,294,967,296)로 오버플로우가 날 것이다.

이렇게 큰 수의 출력이 나올 때는 8바이트 크기인 2^64(18,446,744,073,709,551,616) 자료형을 사용해야한다.

 

여담(C# 64Bit 자료형)

C#에서는 64bit인 정수 자료형이 다음과 같이 존재한다.

Int64와 long 키워드이다.

그런데 사실 vs에서 뜯어보면 두 개는 같은걸 가르키는걸 알 수 있다.

둘 다 System.Int64형태를 가르키는걸 볼 수 있다.

그럼 long과 Int64 키워드를 왜 두 개로 분리하였을까?

프로그래밍 관례적으로 안에 있는 필드나 메소드를 사용하는 경우엔 Int64로 호출하는 것이 좀 더 정확하다고 한다.

하지만 관례는 상대적이기 때문이기 때문에 어느 회사에 들어가서 코드의 스타일이 뭔지에 따라 똑같이 적용하면 될 것으로 보인다.