자유이용권 - 백준 BOJ 25635

 

25635번: 자유 이용권 (acmicpc.net)

25635번: 자유 이용권

 

 

---

풀이

 

이전에 포스팅 했던 INFP 두람 문제와 거의 똑같은 유형이다. 관련된 자세한 풀이는 해당 글을 참조하면 좋을 것 같다

 

 

INFP 두람 문제가 원순열이었다면, 이 문제는 원순열의 조건을 따지지 않아도 된다는것이 차이점

그리고 가능 여부가 아닌 최대값을 구하는 것 또한 차이점이다

 

주어진 입력값에 대해, 연속되는 날에 같은 이용권을 사용하지 않고 최대로 이용 가능한 날짜의 예시를 살펴보자

 

2
1 1 3	// 순서대로 A B C 라 하겠다

// C A C B C 로, 5가 최대

================================

2
3 5	// 순서대로 A B

// B A B A B A B 로 7이 최대

================================

4
2 2 2 3	// 순서대로 A B C D

// A B C D A D B C D 로 9가 최대

 

 

INFP 두람 문제와 마찬가지로, 개수 중 최대인것과 전체 합의 절반과 비교를 하면 되는 문제임을 알 수 있다

 

다만 주의해야 할 것은, 원순열에서는 끝과 처음과의 중복여부도 확인해야 했으므로, 전체 합의 홀짝 여부 상관없이 전체합 / 2 와의 비교가 성립했지만,

이번에는 원순열이 아니므로, 홀수일 경우 전체 합 / 2 + 1 과 비교를 해야한다

 

// 전체 합이 5(홀수) 일 때

? ? ? ? ?
X ? X ? X

// 개수가 제일 많은 종류는, 전체가 5(홀수) 일 때 3개( 5/2 + 1 )까지 들어갈 수 있다

======================================================================

// 전체 합이 4(짝수) 일 때

? ? ? ?
X ? X ?
? X ? X

// 전체가 4(짝수) 일 때 2개( 4/2 )까지 들어갈 수 있다

 

 

따라서 전체 합의 홀짝 여부를 따져, 최대 개수가 임계치 이하일경우 전체합을 그대로 출력하면 되고,

임계치 초과일 경우, 원순열이 아니므로 전체 합에서 최대 개수를 제외한 값에, 2배를 해준 값에 1을 더한 값을 출력해주면 된다.

 

2
2 7	// 순서대로 A B

// 전체합이 9, 최대개수가 7, [ 9/2 + 1 < 7 ] 이므로 B 는 자유롭게 사용가능
// A A
// 위와 같이 A 전부가 사용되었을 때, 최대로 날짜를 늘리는 방법은 양옆과 중간을 모두 B로 채우는것
// B A B A B
// 따라서 최대는 5( (9 - 7) * 2 + 1 ) 이다

 

 

풀이는 증명되었다,

근데 신나게 코드를 작성하고 제출을 해보면 틀렸다고 나오는 사람도 있을 것 이다 ( 나 )

 

이유인 즉슨 이용권 종류 별 최대 개수가 10^9 이다

종류의 최대 개수가 100,000 임을 감안하면 전체합에서 int 타입을 사용했을 경우 오버플로우가 발생할 수 있다

 

또 입력값을 안봤어? 그럼 맞아야지

 

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        long[] ticketCount = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        long ticketCountSum = Arrays.stream(ticketCount).sum();
        long largestTicketCount = Arrays.stream(ticketCount).reduce(0, Math::max);

        long maxValidLargestTicketCount = ticketCountSum % 2 == 0 ? ticketCountSum / 2 : ticketCountSum / 2 + 1;

        if(maxValidLargestTicketCount < largestTicketCount) {
            System.out.println( (ticketCountSum - largestTicketCount) * 2 + 1 );
            return;
        }

        System.out.println(ticketCountSum);
    }
}